I tried to implement the Trie and dfs with backtracking to solve the LeetCode problem Word Search II, but it keeps telling me my dfs method is out of bounds:
class Solution {
class TrieNode{
TrieNode[] children = new TrieNode[26];
String word;
}
public TrieNode buildTrie(String[] words){
TrieNode root =new TrieNode();
for(String w:words){
TrieNode current=root;
for(char c: w.toCharArray()){
int i = c-'a';
if(current.children[i]==null)
current.children[i]=new TrieNode();
current=current.children[i];
}
current.word=w;
}
return root;
}
public List<String> findWords(char[][] board, String[] words) {
List<String> result = new ArrayList();
TrieNode root = buildTrie(words);
for(int i=0; i<board.length; i++){
for(int j=0; i<board[0].length; j++){
dfs(board,i,j,root,result);
}
}
return result;
}
private void dfs(char[][] board, int i, int j, TrieNode root, List<String> result){
char c = board[i][j];
if(c == '*'|| root.children[c-'a']==null)
return;
root= root.children[c-'a'];
if(root.word != null){
result.add(root.word);
root.word = null; //de-duplication
}
board[i][j] = '*';
if(i>0) dfs(board, i-1,j, root, result); //up
if(j>0) dfs(board, i, j-1, root,result);//left
if(i<board.length-1) dfs(board, i+1, j, root, result);//down
if(j<board[0].length-1) dfs(board, i, j+1, root, result);//right
board[i][j]=c; //backtrack
}
}
and here is the error I kept receiving:
java.lang.ArrayIndexOutOfBoundsException: Index 4 out of bounds for length 4
at line 32, Solution.dfs
at line 26, Solution.findWords
at line 54, __DriverSolution__.__helper__
at line 87, __Driver__.main
The error happens at line char c = board[i][j]. I believe my double for loops are within the available range so it should be impossible that there is a OutOfBoundException happening at that specific line.
