Word Search Problem Solution: Given an m x n
grid of characters board
and a string word
, return true
if word
exists in the grid.
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true
Table of Contents
Word Search Problem Solution
Problem Solution In Python
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == word[0]:
ch, board[i][j] = board[i][j], -1
if self.backtrack(ch, 1, word, board, i, j):
return True
board[i][j] = ch
return False
def backtrack(self, ch, k, word, board, x, y):
if k == len(word):
return True
else:
for x1,y1 in ((x+1,y), (x-1,y), (x, y+1), (x, y-1)):
if 0<=x1<len(board) and 0<=y1<len(board[0]) and board[x1][y1] == word[k]:
ch, board[x1][y1] = board[x1][y1], -1
if self.backtrack(ch, k+1, word, board, x1, y1):
return True
board[x1][y1] = ch
return False
Problem Solution In Java
public boolean exist(char[][] board, String word) {
for(int i=0; i<board.length; i++) {
for(int j=0; j<board[i].length; j++) {
if(helper(board, i, j, 0, word)) return true;
}
}
return false;
}
private boolean helper(char[][] g, int i, int j, int index, String w) {
if(i < 0 || i >= g.length || j < 0 || j >= g[i].length || g[i][j] == '.' || g[i][j] != w.charAt(index)) return false;
if(index == w.length()-1) return true;
char c = g[i][j];
boolean res = false;
g[i][j] = '.';
res = helper(g, i+1, j, index+1, w)
|| helper(g, i-1, j, index+1, w)
|| helper(g, i, j+1, index+1, w)
|| helper(g, i, j-1, index+1, w);
g[i][j] = c;
return res;
}
Problem Solution In C++
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size();
int n = board[0].size();
bool ret = false;
vector<vector<bool>> visited(m, vector<bool> (n, false));
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
dfs(board, word, i, j, 0, visited, ret);
}
}
return(ret);
}
void dfs(vector<vector<char>>& board, string word, int i, int j, int l,
vector<vector<bool>> &visited, bool &ret) {
if(ret || l == word.size()) {
ret = true;
return;
}
int m = board.size();
int n = board[0].size();
if(i < 0 || j < 0|| i>= m || j >= n) {
return;
}
if(word[l] != board[i][j]|| visited[i][j]) {
return;
}
visited[i][j] = true;
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
for(int kk = 0; kk < 4; ++kk) {
int x = i + dx[kk];
int y = j + dy[kk];
dfs(board, word, x, y, l + 1, visited, ret);
}
visited[i][j] = false;
}
};
Problem Solution In C
bool DFS(char** board, int boardSize, int* boardColSize, char* word, int len, int index, int i, int j, bool** visited){
if (index == len ){return 1;}
if ( i < 0 || j < 0 || i >= boardSize || j >= *boardColSize || visited[i][j] || board[i][j] != word[index]) {return 0;}
visited[i][j] = 1;
bool ans = DFS(board, boardSize, boardColSize, word, len, index+1, i+1, j, visited) ||
DFS(board, boardSize, boardColSize, word, len, index+1, i-1, j, visited) ||
DFS(board, boardSize, boardColSize, word, len, index+1, i, j+1, visited) ||
DFS(board, boardSize, boardColSize, word, len, index+1, i, j-1, visited);
visited[i][j] = 0;
return ans;
}
bool exist(char** board, int boardSize, int* boardColSize, char * word){
bool** visited = malloc(sizeof(bool*)*boardSize);
for (int i = 0; i < boardSize; i++){
visited[i] = calloc(*boardColSize,sizeof(bool));
}
int len = strlen(word);
for (int i = 0; i < boardSize; i++){
for (int j = 0 ; j < *boardColSize; j++){
if (DFS(board, boardSize, boardColSize, word, len, 0, i, j, visited)) {return 1;};
}
}
return 0;
}