本文主要是介绍leetcode 97:交错字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
看到该题的第一个想法就是直接使用三个指针，t1表示当前s1的下标 t2表示当前s2的下标 t3表示s3的下标
不过因为可能s1 和s2当前的下标纸箱的值都和s3当前的下标指向的字符相同，所以使用数组存放t1 t2 t3的值
bool isInterleave(std::string s1,std::string s2,std::string s3){int t1=0;int t2=0;int t3=0;int n1=s1.size();int n2=s2.size();int n3=s3.size();std::vector<int> ss1;std::vector<int> ss2;std::vector<int> ss3;if(n1+n2!=n3)return false;while(t3<n3){if(s3[t3]==s2[t2]&&s3[t3]==s1[t1]){t3++;t1++;ss1.push_back(t1-1);ss2.push_back(t2);ss3.push_back(t3-1);}else if(s3[t3]==s1[t1]&&s3[t3]!=s2[t2]) {t3++;t1++;}else if(s3[t3]==s2[t2]&&s3[t3]!=s1[t1]){t3++;t2++;}else if(s3[t3]!=s2[t2]&&s3[t3]!=s1[t1]){if(ss1.size()!=0){t3=ss3.back();t2=ss2.back();t1=ss1.back();ss2.pop_back();ss1.pop_back();ss3.pop_back();t3++;t2++;}elsereturn false;}}return true;
}不过这种方式时间复杂度比较高
第二种方式 ，一般字符串的题都可以使用动态规划 使用动态规划的方式
bool isInterleave(std::string s1,std::string s2,std::string s3){int n1=s1.size();int n2=s2.size();int n3=s3.size();if(n1+n2!=n3)return false;if(n1==0&&n2!=0){for(int i=0;i<s2.size();i++){if(s2[i]!=s3[i])return false;}return true;}else if(n1!=0&&n2==0){for(int i=0;i<s1.size();i++){if(s1[i]!=s3[i])return false;}return true;}else if(n1==0&&n2==0)return true;std::vector<std::vector<int>> ss;std::vector<int> a(n2+1);for(int i=0;i<n1+1;i++){ss.push_back(a);}for(int i=1;i<n1+1;i++){if(s1[i-1]==s3[i-1])ss[i][0]=1;elsebreak;}for(int j=1;j<n2+1;j++){if(s2[j-1]==s3[j-1])ss[0][j]=1;elsebreak;}int i=1;int j=1;for(;i<n1+1;i++){for(j=1;j<n2+1;j++){if(ss[i][j-1]==1&&s3[i+j-1]==s2[j-1])ss[i][j]=1;else if(ss[i-1][j]==1&&s3[i+j-1]==s1[i-1])ss[i][j]=1;else if(ss[i-1][j-1]==1){if(s3[i+j-2]==s1[i-1]&&s3[i+j-1]==s2[j-1])ss[i][j]=1;else if(s3[i+j-2]==s2[j-1]&&s3[i+j-1]==s1[i-1])ss[i][j]=1;}}}return ss[i-1][j-1];
}
这篇关于leetcode 97:交错字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
