LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 从每个元素出发，只要有一条路径满足结果即可。标记走过的路径，如果走不通则撤销标记，回溯到上一次的状态

class Solution {
 public:
  bool exist(vector<vector<char>>& board, string word) {
    if (empty(board) || empty(board[0]) || empty(word)) {
      return false;
    }
    for (int i = 0; i < size(board); ++i) {
      for (int j = 0; j < size(board[0]); ++j) {
        if (dfs(board, i, j, word, 0)) {
          return true;
        }
      }
    }
    return false;
  }

  bool dfs(vector<vector<char>>& board, int i, int j, string_view word, int n) {
    if (board[i][j] != word[n]) {
      return false;
    }
    if (n == size(word) - 1) {
      return true;
    }
    char t = board[i][j];
    board[i][j] = '#';                                 // 标记走过的位置
    if (i > 0 && dfs(board, i - 1, j, word, n + 1)) {  // 向上
      return true;
    }
    if (i + 1 < size(board) && dfs(board, i + 1, j, word, n + 1)) {  // 向下
      return true;
    }
    if (j > 0 && dfs(board, i, j - 1, word, n + 1)) {  // 向左
      return true;
    }
    if (j + 1 < size(board[0]) && dfs(board, i, j + 1, word, n + 1)) {  // 向右
      return true;
    }
    board[i][j] = t;  // 四个方向都不通，撤销当前位置的标记
    return false;
  }
};