Why is my BFS solution much slower than DFS ?


  • 0
    T

    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;
        
        Queue<int[]> st = new LinkedList<int[]>();
        st.add(new int[]{0,0});
        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;
    }
    

    }


Log in to reply
 

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