单词搜索 (opens new window)

• 难度：Medium
• 标签：回溯

刷题思路

• [x] 回溯
• [ ] xx

方法 1 回溯

• 复杂度：
  • 时间 O(m*n*(3^l)). 3^l 指 3 个方向搜索单词长度 l 次.
  • 空间 O(m*n). 递归调用栈所用空间为 O(min(l, m*n))
• 结果：
  • 执行用时：104 ms, 在所有 JavaScript 提交中击败了87.53%的用户
  • 内存消耗：40.8 MB, 在所有 JavaScript 提交中击败了41.41%的用户

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    const [m, n] = [board.length, board[0].length]
    for (let i=0; i<m; i++) {
        for (let j=0; j<n; j++) {
            const flag = find(board, i, j, word, 0)
            if (flag) return true
        }
    }
    return false
};

function find (board, i, j, word, curr) {
    if (i>=board.length || i<0) return false
    if (j>=board[0].length || j<0) return false
    const letter = board[i][j]
    if (letter!==word[curr]) return false // 匹配失败
    if (curr===word.length-1) return true // 完全匹配成功

    // 本轮匹配成功，继续推进
    board[i][j] = null // 置空当前作为标记
    const res = find(board, i-1, j, word, curr+1) ||
          find(board, i+1, j, word, curr+1) ||
          find(board, i, j-1, word, curr+1) ||
          find(board, i, j+1, word, curr+1)
    board[i][j] = letter // 运算结束后复位
    return res
}

方法 2

• 复杂度：
  • 时间 O()
  • 空间 O()

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~