79. Word Search

source: https://leetcode.com/problems/word-search/

Question

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

思路

对于一个点，从上下左右四个方向开始寻找，同时记录已寻找过的点，避免重复寻找。

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
    const visited = board.map(line => line.map(() => false));
    const check = (position, words) => {
        const [y, x] = position;
        const char = board[y][x];
        if (char !== words[0]) return false;
        const arr = Array.from(words);
        arr.shift();
        if (!arr.length) return true;
        visited[y][x] = true;
        const positions = [[y - 1, x], [y, x - 1], [y + 1, x], [y, x + 1]].filter(v => board[v[0]]?.[v[1]] !== undefined && !visited[v[0]][v[1]]);
        for (let i = 0; i < positions.length; i++) {
            const exist = check(positions[i], arr.join(''));
            if (exist) {
                visited[y][x] = false;
                return true;
            }
        }
        visited[y][x] = false;
        return false;
    };
    for (let y = 0; y < board.length; y++) {
        for (let x = 0; x < board[y].length; x++) {
            const exist = check([y, x], word);
            if (exist) return true;
        }
    }
    return false;
};

总结

这题如果用直接的回溯法的话，很明显太浪费了。

需要对回溯法做一些限制/优化。