4ms c++ solution with queue and BFS


  • 0
    Z

    I use two vectors to work like a queue to save the the index of s1 and s2;
    use a table of s1.length()*s2.length() to show whether the element is already in the queue;
    and do the BFS;

    bool helper(string &s1,string &s2,string &s3){
        int l1=s1.length(),l2=s2.length();
        vector<int> q1,q2;//queue;
        bool table[s1.length()+1][s2.length()+1]={false};
        char c1,c2,c3;
        
        q1.push_back(0);
        q2.push_back(0);
        table[0][0]=true;
        
        while(q1.size()){
            int tmp1=q1[0],tmp2=q2[0];
            if(tmp1==l1&&tmp2==l2)return true;
            
            
            if(tmp1==l1)c1='0';
            else c1=s1[tmp1];
            if(tmp2==l2)c2='0';
            else c2=s2[tmp2];
            c3=s3[tmp1+tmp2];
            
            
            q1.erase(q1.begin());
            q2.erase(q2.begin());
            table[tmp1][tmp2]=false;
            
            if(c1==c3){
                if(table[tmp1+1][tmp2]==false){
                    q1.push_back(tmp1+1);
                    q2.push_back(tmp2);
                    table[tmp1+1][tmp2]=true;
                }
            }
            if(c2==c3){
                if(table[tmp1][tmp2+1]==false){
                    q1.push_back(tmp1);
                    q2.push_back(tmp2+1);
                    table[tmp1][tmp2+1]=true;
                }
            }
            
        }
        return false;
    }
    bool isInterleave(string s1, string s2, string s3) {
        if(s1.length()+s2.length()!=s3.length())return false;
        if(s1.length()==0)return true;
        return helper(s1,s2,s3);
    }

Log in to reply
 

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