# Time Limit Exceeded Last executed input: ["aaaa","aaaa","aaaa","aaaa","aaab"], "aaaaaaaaaaaaaaaaaaaa"

• My code works in local, but not in OJ. My idea is simply do a DFS for every qualified entry and return true if find a valid path. I use hashset to record visited nodes. Below is the code. Thanks

`````` public class Solution {
public class pos{
int i;
int j;
public pos(int _i,int _j){
i=_i;
j=_j;
}
public int hashCode(){
return 197*i+37*j;
}
public boolean equals(Object p1){
pos p2 = (pos) p1;
if(i==p2.i&&j==p2.j)return true;
return false;
}
}

public boolean DFS(char[][] board, int i, int j, String word, HashSet<pos> set){
//break condition
if(word==null || word.length()==0) return true;
//check if position<i,j> is out of boundary
if(i<0||i>=board.length||j<0||j>=board[0].length) return false;
//check if the character in current position<i,j> equals to the first character in word
if(board[i][j] != word.charAt(0)) return false;
//create a new set object with all previous visited nodes
HashSet<pos> newSet = new HashSet<pos>(set);
//check if <i,j> is visited or not
//remove first character from word, recursively check four adjacency directions
String s = word.substring(1);
return DFS(board,i+1,j,s,newSet) || DFS(board,i-1,j,s,newSet) || DFS(board,i,j-1,s,newSet) || DFS(board,i,j+1,s,newSet);
}
return false;
}
public boolean exist(char[][] board, String word) {
if(board==null)return false;
if(word==null) return true;
//if word length bigger than board size, simply return false
if(word.length()>board.length*board[0].length)return false;
//traverse board, return true when find a valid path
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
if(DFS(board,i,j,word, new HashSet<pos>())) return true;
}
}
return false;
}
}``````

• I've updated my post per your request. Thank you for your time!

• I am not familiar with Java, but I think you are wasting large time on new a set object, i.e. this statement `HashSet<pos> newSet = new HashSet<pos>(set);`.

So I try to change part of your code from

``````    //create a new set object with all previous visited nodes
HashSet<pos> newSet = new HashSet<pos>(set);
//check if <i,j> is visited or not
//remove first character from word, recursively check four adjacency directions
String s = word.substring(1);
return DFS(board,i+1,j,s,newSet) || DFS(board,i-1,j,s,newSet) || DFS(board,i,j-1,s,newSet) || DFS(board,i,j+1,s,newSet);
}
``````

to

``````    pos now = new pos(i,j);
//check if <i,j> is visited or not
//remove first character from word, recursively check four adjacency directions
String s = word.substring(1);
if (DFS(board,i+1,j,s,set) || DFS(board,i-1,j,s,set) || DFS(board,i,j-1,s,set) || DFS(board,i,j+1,s,set)) {
return true;
}
set.remove(now);
}
``````

Then, it passed.

However, I do not think it is necessary to create a `pos` object to do the hash set check. All you need is a 2d matrix, `boolean mark[board.size][board[0].size]`.

• Thanks for your suggestion, 2d matrix does make things easier. I should've thought of that first. Appreciate your help!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.