# Why is my BFS solution much slower than DFS ?

• if I simply change the following queue to stack, thus changing BFS to DFS, the code runs much faster.
right now on OJ it times out , though runs with correct results on eclipse, with longer time.

``````public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
// return recursive(s1.toCharArray(),s2.toCharArray(),s3.toCharArray(),  0, 0, 0);
char ss1[] = s1.toCharArray();
char ss2[] = s2.toCharArray();
char ss3[] = s3.toCharArray();

boolean ok[][] = new boolean[ss1.length+1][ss2.length+1];

if (ss1.length + ss2.length != ss3.length) return false;

boolean used[][] = new boolean[ss1.length+1][ss2.length+1];
int []xy;
while((xy = st.poll()) != null) {
// int [] xy = st.remove();
int i = xy[0];
int j = xy[1];
used[i][j] = true;
if (i==ss1.length && j==ss2.length) return true;
if (i < ss1.length && ss1[i] == ss3[i+j] && !used[i+1][j]) st.add(new int[]{i+1,j});
if (j < ss2.length && ss2[j] == ss3[i+j] && !used[i][j+1]) st.add(new int[]{i, j+1});
}

return false;
}
``````

}

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