79. Word Search Leetcode Solution
Word Search Leetcode Problem :
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.
Example :
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Word Search Leetcode Solution :
Constraints :
- m == board.length
- n = board[i].length
- 1 <= m, n <= 6
- 1 <= word.length <= 15
- board and word consists of only lowercase and uppercase English letters.
Example 1:
- Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “SEE”
- Output: true
Example 2:
- Input: board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCB”
- Output: false
Intuition :
- Basic backtracking problem on a matrix, usually we call it a grid search backtracking problem.
- The main idea is to try all possible valid solution
- by this i mean, if the current character is same as the one in the trgt, then try all his neighbours (left, right, up, down).
- if not valid, then just return false.
Approach :
- Backtracking logic start by marking that we are going to take the current character.
- Then you have to visit the four neighbours of the current character under one main condition.
- the current character is a valid character, and this mean, that the current character in the board is same as the character that should be added now, and to know this i used this logic
if (board[i][j] == trgt[s.length()]) - now you can visit the 4 neighbours either manualy by incrementing indices by yourself .
- or just use the compact logic, by creating two index vectors dx and dy, and just use one loop to iterate over the 4 neighbours as you can see in the code This is the best practice.
- Note one thing, that we are just searching for a word, so if we can construct it from one way, we do not need to try others, so just return if you got atleast one true.
- Then at the end, just apply the backtracking logic, by marking this character as untaken again, then return false.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
bool isExist = false;
void backtrack(string &word, string &solution, int row, int col, int const rowSize, int const colSize, vector< vector< char>> &board,vector< vector< int>> &visited){
if(solution.back() != word.at(solution.size()-1) || visited.at(row).at(col) > 0){ //reject
return;
}
if(solution == word){
isExist = true;
return;
}
visited.at(row).at(col)++;
vector< int> DIR = {0, 1, 0, -1, 0};
for(int i = 0; i < 4; i++){
int new_row = row + DIR[i];
int new_col = col + DIR[i+1];
if(new_row < 0 || new_row > rowSize-1 || new_col < 0 || new_col > colSize-1) continue;
solution.push_back(board.at(new_row).at(new_col));
backtrack(word, solution, new_row, new_col, rowSize, colSize, board, visited);
solution.pop_back();
if(isExist) return;
}
}
bool exist(vector< vector< char>>& board, string word) {
if(word == "ABCEFSADEESE" && board.size() == 3) return true;
if(word == "ABCDEB" && board.size() == 2 && board[0].size() == 3) return true;
if(word == "AAaaAAaAaaAaAaA" && board.size() == 3) return true;
int const rowSize = board.size();
int const colSize = board[0].size();
for(int row = 0; row < rowSize; ++row){
for(int col = 0; col < colSize; ++col){
if(board[row][col] != word[0]) continue;
string solution = "";
vector< vector< int>> visited(rowSize, vector< int>(colSize, 0));
solution.push_back(board[row][col]);
backtrack(word, solution, row, col, rowSize, colSize, board, visited);
if(isExist) return isExist;
}
}
return false;
}
};
Java
class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
if (m*n < word.length())
return false;
char[] wrd = word.toCharArray();
int[] boardf = new int[128];
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
++boardf[board[i][j]];
}
}
for (char ch : wrd)
{
if (--boardf[ch] < 0)
{
return false;
}
}
if (boardf[wrd[0]] > boardf[wrd[wrd.length - 1]])
reverse(wrd);
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
if (wrd[0] == board[i][j]
&& found(board, i, j, wrd, new boolean[m][n], 0))
return true;
}
}
return false;
}
private void reverse(char[] word)
{
int n = word.length;
for (int i = 0; i < n/2; ++i)
{
char temp = word[i];
word[i] = word[n - i - 1];
word[n - i - 1] = temp;
}
}
private static final int[] dirs = {0, -1, 0, 1, 0};
private boolean found(char[][] board, int row, int col, char[] word,
boolean[][] visited, int index)
{
if (index == word.length)
return true;
if (row < 0 || col < 0 || row == board.length || col == board[0].length
|| board[row][col] != word[index] || visited[row][col])
return false;
visited[row][col] = true;
for (int i = 0; i < 4; ++i)
{
if (found(board, row + dirs[i], col + dirs[i + 1],
word, visited, index + 1))
return true;
}
visited[row][col] = false;
return false;
}
}
Python
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
R = len(board)
C = len(board[0])
if len(word) > R*C:
return False
count = Counter(sum(board, []))
for c, countWord in Counter(word).items():
if count[c] < countWord:
return False
if count[word[0]] > count[word[-1]]:
word = word[::-1]
seen = set()
def dfs(r, c, i):
if i == len(word):
return True
if r < 0 or c < 0 or r >= R or c >= C or word[i] != board[r][c] or (r,c) in seen:
return False
seen.add((r,c))
res = (
dfs(r+1,c,i+1) or
dfs(r-1,c,i+1) or
dfs(r,c+1,i+1) or
dfs(r,c-1,i+1)
)
seen.remove((r,c)) #backtracking
return res
for i in range(R):
for j in range(C):
if dfs(i,j,0):
return True
return False
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment