剑指Offer题解 - Day30

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
const dfs = (board, word, i, j, k) => {
    if (i >= board.length || i < 0
    || j >= board[0].length || j < 0
    || board[i][j] !== word[k]) return false;
    if (k === word.length - 1) return true;
    board[i][j] = '';
    let result = dfs(board, word, i + 1, j, k + 1)
       || dfs(board, word, i - 1, j, k + 1)
       || dfs(board, word, i, j + 1, k + 1)
       || dfs(board, word, i, j - 1, k + 1)
  board[i][j] = word[k];
    return result;
}

const exist = (board, word) => {
    let words = word.split(''); // 分割字符串为数组
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (dfs(board, words, i, j, 0)) return true; // 调用DFS进行查找
        }
    }
    return false; // 没找到最终返回false
};