# Word Search Problem Solution

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

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