The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example, given the following board:
[
['A','B','C','E'],
['S','F','C' ['A','D','E','E']
exists(board, "ABCCED") returns true, exists(board, "SEE") returns true, exists(board, "ABCB") returns false.
Python
def exist(board, word):
if not board:
return False
def dfs(board, word, i, j, k):
if k == len(word):
return True
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[k]:
return False
temp = board[i][j]
board[i][j] = '#' # mark as visited
res = (dfs(board, word, i+1, j, k+1) or
dfs(board, word, i-1, j, k+1) or
dfs(board, word, i, j+1, k+1) or
dfs(board, word, i, j-1, k+1))
board[i][j] = temp # unmark
return res
for i in range(len(board)):
for j in range(len(board[0])):
if dfs(board, word, i, j, 0):
return True
return False
# Example usage
board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
print(exist(board, "ABCCED")) # returns True
print(exist(board, "SEE")) # returns True
print(exist(board, "ABCB")) # returns False
Java
public class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0) return false;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, word, i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int i, int j, int k) {
if (k == word.length()) return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(k)) {
return false;
}
char temp = board[i][j];
board[i][j] = '#'; // mark as visited
boolean res = dfs(board, word, i + 1, j, k + 1) ||
dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) ||
dfs(board, word, i, j - 1, k + 1);
board[i][j] = temp; // unmark
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
char[][] board = {
{'A','B','C','E'},
{'S','F','C','S'},
{'A','D','E','E'}
};
System.out.println(solution.exist(board, "ABCCED")); // returns True
System.out.println(solution.exist(board, "SEE")); // returns True
System.out.println(solution.exist(board, "ABCB")); // returns False
}
}
Javascript:
var exist = function(board, word) {
if (!board || board.length === 0) return false;
function dfs(board, word, i, j, k) {
if (k === word.length) return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] !== word[k]) {
return false;
}
const temp = board[i][j];
board[i][j] = '#'; // mark as visited
const res = dfs(board, word, i + 1, j, k + 1) ||
dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) ||
dfs(board, word, i, j - 1, k + 1);
board[i][j] = temp; // unmark
return res;
}
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
if (dfs(board, word, i, j, 0)) {
return true;
}
}
}
return false;
};
// Example usage
const board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
];
console.log(exist(board, "ABCCED")); // returns true
console.log(exist(board, "SEE")); // returns true
console.log(exist(board, "ABCB")); // returns false
Asked by Coursera.