79. Word Search

[Tcdian]

79. Word Search

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

Example

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Note

• board 和 word 中只包含大写和小写英文字母。
• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• 1 <= word.length <= 10^3

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    const visited = '*';
    const direction = [-1, 0, 1, 0, -1];
    let result = false;
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            dfs([i, j], 0);
        }
    }
    return result;

    function dfs([x, y], wordIndex) {
        const currentVal = board[x][y];
        if (result) {
            return;
        }
        if (currentVal === visited || currentVal !== word[wordIndex]) {
            return;
        }
        if (wordIndex === word.length - 1) {
            result = true
            return;
        }
        board[x][y] = visited;
        for (let i = 0; i < 4; i++) {
            const directionX = x + direction[i];
            const directionY = y + direction[i + 1];
            if (
                directionX >= 0 && directionX < board.length
                    && directionY >= 0 && directionY < board[0].length
            ) {
                dfs([directionX, directionY], wordIndex + 1);
            }
        }
        board[x][y] = currentVal;
    }
};

• TypeScript Solution

function exist(board: string[][], word: string): boolean {
    const visited = '*';
    const direction = [-1, 0, 1, 0, -1];
    let result = false;
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            dfs([i, j], 0);
        }
    }
    return result;

    function dfs([x, y]: [number, number], wordIndex: number) {
        const currentVal = board[x][y];
        if (result) {
            return;
        }
        if (currentVal === visited || currentVal !== word[wordIndex]) {
            return;
        }
        if (wordIndex === word.length - 1) {
            result = true
            return;
        }
        board[x][y] = visited;
        for (let i = 0; i < 4; i++) {
            const directionX = x + direction[i];
            const directionY = y + direction[i + 1];
            if (
                directionX >= 0 && directionX < board.length
                    && directionY >= 0 && directionY < board[0].length
            ) {
                dfs([directionX, directionY], wordIndex + 1);
            }
        }
        board[x][y] = currentVal;
    }
};