Problem:
You are given a 2-d array of letters a-zA-Z. Words can be constructed from neighboring cells in the 2-d array. The current cell's neighboring cells are the ones on top, bottom, left and right. One cell can be used only once for a word.Check if a given word can be constructed from the given 2-d array.
For Example, Given array
[
['A','B','E','D'],
['E','F','E','H'],
['I','J','K','L']
]
word "BEE" can be constructed, so return true.
"SEE" can not be constructed, so return false.
"ABFE", return true.
"KEHD", return true.
"KLHEK", return false.
Solution:
At the first impression, this is a graph dfs traversal problem. We can start at each grid cell, do a dfs search for the word sequence. A second thought suggests that this problem is more than graph dfs. Our goal is to search the right path matching the word among all the possible dfs traversal paths. So we are actually doing the path permutation, and we need to use backtrack. That is to say, when we visit a node, if that visit turns out to be a wrong move, we should track back, unmark the node, then give another neighboring node a try.
Two small techniques we need to pay attention in the following code.
1. In order to visit all the neighbor nodes, we create a row mask and a column mask
int[] rowmask = new int[1, 0, -1, 0];
int[] colmask = new int[0, 1, 0, -1];
for(int i = 0; i < 4; i++) {
int i = row + rowmask[d];
int j = col + colmask[d];
...
}
the i and j combinations will cover all the 4 neighbors.
2. we don't have to use a set to keep track of visited node. We can just set the visited node to any character that is not a-zA-Z, that way we saved row*col memory that the set need. The drawback of this approach is side effect, the original 2D array has been modified.
3. we check word.length() == index at the first line, that way, even we are given a one element array, the function still works without throwing java.lang.StringIndexOutOfBoundsException.
import java.util.*;
class Solution {
private Set<Integer> visited = new HashSet<>();
public boolean found(char[][] board, String word) {//"KEHD"
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
visited = new HashSet<>();
if(dfs(board, word, 0, i, j))
return true;
}
}
return false;
}
private boolean dfs(char[][] board, String word, int index, int row, int col) {
if(word.length() == index) {
return true;
}
if((row < 0 || row == board.length || col < 0 || col == board[0].length) || word.charAt(index) != board[row][col])
return false;
visited.add(row*board[0].length + col);//10
//board[row][col] = '!';
int[] rowmask = new int[] {0, 1, 0, -1};
int[] colmask = new int[] {1, 0, -1, 0};
for(int d = 0; d < 4; d++) {
int i = row + rowmask[d];
int j = col + colmask[d];
if(!visited.contains(i*board[0].length + j)) {
if(dfs(board, word, index + 1, i, j))
return true;
}
}
visited.remove(row*board[0].length + col);//unmark
//board[row][col] = word.charAt(index);
return false;
}
public static void main(String[] args) {
char[][] board = new char[][]{
{'A','B','E','D'},
{'E','F','E','H'},
{'I','J','K','L'}
};
printBoard(board);
Solution sol = new Solution();
System.out.println(sol.found(board, "BEE"));
System.out.println(sol.found(board, "SEE"));
System.out.println(sol.found(board, "ABFE"));
System.out.println(sol.found(board, "KEHD"));
System.out.println(sol.found(board, "KLHEK"));
System.out.println(sol.found(board, "A"));
printBoard(board);
}
private static void printBoard(char[][] board) {
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
System.out.print(String.format("%3s", board[i][j]));
}
System.out.println();
}
}
}
class Solution {
private Set<Integer> visited = new HashSet<>();
public boolean found(char[][] board, String word) {//"KEHD"
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
visited = new HashSet<>();
if(dfs(board, word, 0, i, j))
return true;
}
}
return false;
}
private boolean dfs(char[][] board, String word, int index, int row, int col) {
if(word.length() == index) {
return true;
}
if((row < 0 || row == board.length || col < 0 || col == board[0].length) || word.charAt(index) != board[row][col])
return false;
visited.add(row*board[0].length + col);//10
//board[row][col] = '!';
int[] rowmask = new int[] {0, 1, 0, -1};
int[] colmask = new int[] {1, 0, -1, 0};
for(int d = 0; d < 4; d++) {
int i = row + rowmask[d];
int j = col + colmask[d];
if(!visited.contains(i*board[0].length + j)) {
if(dfs(board, word, index + 1, i, j))
return true;
}
}
visited.remove(row*board[0].length + col);//unmark
//board[row][col] = word.charAt(index);
return false;
}
public static void main(String[] args) {
char[][] board = new char[][]{
{'A','B','E','D'},
{'E','F','E','H'},
{'I','J','K','L'}
};
printBoard(board);
Solution sol = new Solution();
System.out.println(sol.found(board, "BEE"));
System.out.println(sol.found(board, "SEE"));
System.out.println(sol.found(board, "ABFE"));
System.out.println(sol.found(board, "KEHD"));
System.out.println(sol.found(board, "KLHEK"));
System.out.println(sol.found(board, "A"));
printBoard(board);
}
private static void printBoard(char[][] board) {
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
System.out.print(String.format("%3s", board[i][j]));
}
System.out.println();
}
}
}
The time complexity is O(N*(4^L)), where N is the total number of elements in the array and L is the word length. In the worst case, we do the dfs traversal for all the N cells. During each dfs traversal, we could find mismatch at the last word character, at each step we need to check 4 neighbors, so the cost is 4^L. The space complexity is O(L) which is the max depth of the dfs calling stack.
