Skip to content

79. Word Search 👍

  • Time: $O(mn4^{|\texttt{word}|})$
  • Space: $O(4^{|\texttt{word}|})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  bool exist(vector<vector<char>>& board, string word) {
    for (int i = 0; i < board.size(); ++i)
      for (int j = 0; j < board[0].size(); ++j)
        if (dfs(board, word, i, j, 0))
          return true;
    return false;
  }

 private:
  bool dfs(vector<vector<char>>& board, const string& word, int i, int j,
           int s) {
    if (i < 0 || i == board.size() || j < 0 || j == board[0].size())
      return false;
    if (board[i][j] != word[s] || board[i][j] == '*')
      return false;
    if (s == word.length() - 1)
      return true;

    const char cache = board[i][j];
    board[i][j] = '*';
    const bool isExist = dfs(board, word, i + 1, j, s + 1) ||
                         dfs(board, word, i - 1, j, s + 1) ||
                         dfs(board, word, i, j + 1, s + 1) ||
                         dfs(board, word, i, j - 1, s + 1);
    board[i][j] = cache;

    return isExist;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public boolean exist(char[][] board, String word) {
    for (int i = 0; i < board.length; ++i)
      for (int j = 0; j < board[0].length; ++j)
        if (dfs(board, word, i, j, 0))
          return true;
    return false;
  }

  private boolean dfs(char[][] board, String word, int i, int j, int s) {
    if (i < 0 || i == board.length || j < 0 || j == board[0].length)
      return false;
    if (board[i][j] != word.charAt(s) || board[i][j] == '*')
      return false;
    if (s == word.length() - 1)
      return true;

    final char cache = board[i][j];
    board[i][j] = '*';
    final boolean isExist = dfs(board, word, i + 1, j, s + 1) || //
                            dfs(board, word, i - 1, j, s + 1) || //
                            dfs(board, word, i, j + 1, s + 1) || //
                            dfs(board, word, i, j - 1, s + 1);
    board[i][j] = cache;

    return isExist;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def exist(self, board: list[list[str]], word: str) -> bool:
    m = len(board)
    n = len(board[0])

    def dfs(i: int, j: int, s: int) -> bool:
      if i < 0 or i == m or j < 0 or j == n:
        return False
      if board[i][j] != word[s] or board[i][j] == '*':
        return False
      if s == len(word) - 1:
        return True

      cache = board[i][j]
      board[i][j] = '*'
      isExist = (dfs(i + 1, j, s + 1) or
                 dfs(i - 1, j, s + 1) or
                 dfs(i, j + 1, s + 1) or
                 dfs(i, j - 1, s + 1))
      board[i][j] = cache

      return isExist

    return any(dfs(i, j, 0)
               for i in range(m)
               for j in range(n))