79.单词搜索

链接：79.单词搜索
难度：Medium
标签：数组、字符串、回溯、矩阵
简介：给定一个二维网格和一个单词，找出该单词是否存在于网格中。

题解 1 - typescript

• 编辑时间：2020-09-13
• 执行用时：168ms
• 内存消耗：44.1MB
• 编程语言：typescript
• 解法介绍：深度优先搜索。

function exist(board: string[][], word: string): boolean {
  const rowLen = board.length;
  const colLen = board[0].length;
  const used = new Set<string>();
  const format = (row: number, col: number) => `${row}:${col}`;
  const startArr = getStarStArr(word[0]);
  if (startArr.length === 0) return false;
  return find(word, startArr);
  function find(word: string, startArr: [number, number][] = []): boolean {
    if (word.length === 1) {
      for (const [row, col] of startArr) {
        if (board[row][col] === word && !used.has(format(row, col))) return true;
      }
      return false;
    }
    const nextWord = word.substr(1);
    for (const [row, col] of startArr) {
      const formatName = format(row, col);
      if (used.has(formatName)) continue;
      used.add(formatName);
      const arr = findNext(row, col, nextWord[0]);
      if (arr.length === 0) {
      } else if (find(nextWord, arr)) return true;
      used.delete(formatName);
    }
    return false;
  }
  function getStarStArr(char: string): [number, number][] {
    const ans: [number, number][] = [];
    for (let i = 0; i < rowLen; i++)
      for (let j = 0; j < colLen; j++) {
        board[i][j] === char && ans.push([i, j]);
      }
    return ans;
  }
  function findNext(row: number, col: number, char: string): [number, number][] {
    const ans: [number, number][] = [];
    row !== 0 && board[row - 1][col] === char && ans.push([row - 1, col]);
    col !== 0 && board[row][col - 1] === char && ans.push([row, col - 1]);
    row !== rowLen - 1 && board[row + 1][col] === char && ans.push([row + 1, col]);
    col !== colLen - 1 && board[row][col + 1] === char && ans.push([row, col + 1]);
    return ans;
  }
}

题解 2 - cpp

• 编辑时间：2022-02-18
• 执行用时：144ms
• 内存消耗：7.8MB
• 编程语言：cpp
• 解法介绍：dfs。

int dirs[4][2] = {
    {0, 1},
    {0, -1},
    {1, 0},
    {-1, 0},
};
class Solution {
   public:
    int n, m, check[10][10] = {0};
    bool dfs(vector<vector<char>>& board, string& s, int idx, int row,
             int col) {
        if (idx == s.size() - 1) return board[row][col] == s[idx];
        if (s[idx] != board[row][col]) return 0;
        check[row][col] = 1;
        int res = 0;
        for (int i = 0; i < 4; i++) {
            int nrow = row + dirs[i][0], ncol = col + dirs[i][1];
            if (nrow < 0 || nrow >= n || ncol < 0 || ncol >= m ||
                check[nrow][ncol])
                continue;
            if (dfs(board, s, idx + 1, nrow, ncol)) {
                res = 1;
                break;
            }
        }
        check[row][col] = 0;
        return res;
    }
    bool exist(vector<vector<char>>& board, string word) {
        n = board.size();
        m = board[0].size();
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++) {
                if (dfs(board, word, 0, row, col)) return 1;
            }
        }
        return 0;
    }
};