Given an m x n grid of characters board and a string word,
return true if word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Test Cases
Input:
(char[]) board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
(string) word = "ABCCED"
Output:
(boolean) true
Input:
(char[]) board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
(string) word = "See"
Output:
(boolean) true
Input:
(char[]) board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
(string) word = "ABCB"
Output:
(boolean) false
Solution
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int n = board.size(), m = board[0].size();
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if (exist(board, word, i, j, 0)) return true;
}
}
return false;
}
bool exist(vector<vector<char>> &board, string word, int x, int y, int w) {
if (w == word.length()) return true;
if (x < 0 || y < 0 || x == board.size() || y == board[0].size()) return false;
if (board[x][y] != word[w]) return false;
char c = board[x][y];
board[x][y] = '*';
bool res = exist(board, word, x+1, y, w+1)
|| exist(board, word, x, y+1, w+1)
|| exist(board, word, x-1, y, w+1)
|| exist(board, word, x, y-1, w+1);
board[x][y] = c;
return res;
}
};class Solution {
public boolean exist(char[][] board, String word) {
char[] w = word.toCharArray();
for (int y=0; y<board.length; y++) {
for (int x=0; x<board[y].length; x++) {
if (exist(board, y, x, w, 0)) return true;
}
}
return false;
}
private boolean exist(char[][] board, int y, int x, char[] word, int i) {
if (i == word.length) return true;
if (y<0 || x<0 || y == board.length || x == board[y].length) return false;
if (board[y][x] != word[i]) return false;
board[y][x] ^= 256;
boolean exist = exist(board, y, x+1, word, i+1)
|| exist(board, y, x-1, word, i+1)
|| exist(board, y+1, x, word, i+1)
|| exist(board, y-1, x, word, i+1);
board[y][x] ^= 256;
return exist;
}
}from typing import List
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
for i in range(len(board)):
for j in range(len(board[0])):
if self.check(board, word, i, j, 0):
return True
return False
def check(self, board: List[List[str]], word: str, r: int, c: int, pos: int):
if pos == len(word):
return True
if r < 0 or r == len(board) or c < 0 or c == len(board[0]):
return False
if board[r][c] != word[pos]:
return False
board[r][c], orig = '0', board[r][c]
res = self.check(board, word, r + 1, c, pos + 1) or self.check(board, word, r - 1, c, pos + 1) or self.check(
board, word, r, c + 1, pos + 1) or self.check(board, word, r, c - 1, pos + 1)
board[r][c] = orig
return res