Given a 2D board and a word, find if the 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.
Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true Example 2:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false
Constraints:
board and word consists only of lowercase and uppercase English letters. 1 <= board.length <= 200 1 <= board[i].length <= 200 1 <= word.length <= 10^3
public class Solution {
public bool Exist(char[][] board, string word) {
var used = new HashSet<string>();
for(int i=0;i<board.Length;i++){
for(int j=0;j<board[0].Length;j++){
if(board[i][j]==word[0]){
var res = Helper(board,i,j, word, 0, used);
if(res){
return true;
}
}
}
}
return false;
}
private bool Helper(char[][] board, int x, int y, string word,int start, HashSet<string> used){
if(start == word.Length && used.Count()==word.Length){
return true;
}
if(x<0 || x>board.Length-1){
return false;
}
if(y<0 || y > board[0].Length-1){
return false;
}
if(start> word.Length-1){
return false;
}
if(board[x][y]!=word[start]){
return false;
}
if(used.Contains(GetKey(x,y))){
return false;
}
used.Add(GetKey(x,y));
bool result = false;
int x1 = x-1;
int y1 = y;
result = result || Helper(board, x1, y1, word, start+1, used);
x1 = x+1;
y1 = y;
result = result || Helper(board, x1, y1, word, start+1, used);
x1 = x;
y1 = y-1;
result = result || Helper(board, x1, y1, word, start+1, used);
x1 = x;
y1 = y+1;
result = result || Helper(board, x1, y1, word, start+1, used);
used.Remove(GetKey(x, y));
return result;
}
private string GetKey(int x, int y){
return x+":"+y;
}
}Time Complexity: O(2^n)
Space Complexity: O(n)
