# 4ms c++ solution with queue and BFS

• 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);
}``````

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