LeetCode Solutions

			

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;
  }
};

			

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;
  }
}

			

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))