题目
97. 交错字符串
我的思路和实现
我的思路是给s1,s2和s3各设置一个指针，用来指示当前待匹配的字符
递归思路解决：
算法应该没有逻辑问题，可是会递归+回溯时间复杂度较大，达到了2^n级别
class Solution { public: bool result; void recursion(string& s1,int i1,string& s2,int i2,string& s3,int i3){ //printf("s1:%d %cn",i1,s1[i1]); //递归终结条件 if(i3==s3.size()&&i1==s1.size()&&i2==s2.size()){ result=true;return;} //当前层处理逻辑 if(i1<s1.size()) if(s1[i1]==s3[i3]) recursion(s1,i1+1,s2,i2,s3,i3+1); //递归到下一层 if(i2<s2.size()) if(s2[i2]==s3[i3]) recursion(s1,i1,s2,i2+1,s3,i3+1); //清除当前层 return; } bool isInterleave(string s1, string s2, string s3) { result = false; recursion(s1,0,s2,0,s3,0); return result; } };
本题官方题解的思路是动态规划：
s1的前i个字符和s2的前j个字符是否能匹配s3的前i+j个字符的条件是：
- s1的前i-1个字符和s2的前j个字符与s3的前i+j-1个字符匹配&&s1的第i个字符与s3的第i+j个字符匹配 或者
- s1的前i个字符和s2的前j-1个字符与s3的前i+j-1个字符匹配&&s2的第j个字符与s3的第i+j个字符匹配
递推到最后的结果得到s3得起整个字符串能否被s1和s2的两个字符串交叉匹配
有点类似与遍历一个m*n的二维数组，每个元素的值取决于其左边和上面相邻的元素的值，时间复杂度为m*n
class Solution { public: bool isInterleave(string s1, string s2, string s3) { auto f = vector <int> (s2.size() + 1, false); int n = s1.size(), m = s2.size(), t = s3.size(); if (n + m != t) { return false; } f[0] = true; for (int i = 0; i <= n; ++i) { for (int j = 0; j <= m; ++j) { int p = i + j - 1; if (i > 0) { f[j] &= (s1[i - 1] == s3[p]); } if (j > 0) { f[j] |= (f[j - 1] && s2[j - 1] == s3[p]); } } } return f[m]; } };
对比我的没有记忆化的递归方法：
- 为什么时间复杂度一个是m*n，一个是2^n?
-
- 个人理解是在我的解决方案中，匹配到s1的第i个字符s2的第j字符时，此时程序中是隐式地记录了具体i+j个字符是怎么交叉排序的（递归函数的调用栈）；而动态规划的解决方案中没有记录前i+j个字符具体是如何交叉排序的，只记录了是否前i+j个字符可以匹配！
对我的思路的改进：
记忆化的递归，用一个全局变量二维数组bool memo[][]来辅助记忆。memo[i][j]记录的是s1的前i个字符和s2的前j个字符是否能交叉匹配s3的前i+j个字符。这样一来大大减少了递归函数的调用次数，总共最多调用m*n次，时间复杂度也降到了m*n。
public: bool result; bool** memo; void recursion(string& s1,int i1,string& s2,int i2,string& s3,int i3){ //printf("s1:%d %cn",i1,s1[i1]); //递归终结条件 if(memo[i1][i2]==false)return; if(i3==s3.size()&&i1==s1.size()&&i2==s2.size()){ result=true;return;} //当前层处理逻辑 if(i1<s1.size()) if(s1[i1]==s3[i3]) recursion(s1,i1+1,s2,i2,s3,i3+1); //递归到下一层 if(i2<s2.size()) if(s2[i2]==s3[i3]) recursion(s1,i1,s2,i2+1,s3,i3+1); //清除当前层 memo[i1][i2]=false; return; } bool isInterleave(string s1, string s2, string s3) { result = false; memo = new bool*[s1.size()+1]; for(int i=0;i<s1.size()+1;i++){ memo[i] = new bool[s2.size()+1]; for(int j=0;j<s2.size()+1;j++){ memo[i][j]=true; }} recursion(s1,0,s2,0,s3,0); return result; } };
拓展学习
C++声明二维数组
转自：C++声明二维数组
#include <iostream> #include <vector> using namespace std; int rows=2,columns=3;
使用一维数组模型二维数组
int a0[] = {1,2,3,4,5,6}; for(int i=0;i<rows;i++){ for(int j=0;j<columns;j++){ cout<<a0[i*columns+j]<<" ";//a0[i*columns+j]等价于a0[i][j] } cout<<endl; }
静态二维数组
int a1[2][3] = {1,2,3,4,5,6};
动态二维数组！要熟练
//申请空间 int** a2 = new int*[rows]; for(int i=0;i<rows;i++) a2[i] = new int[columns]; //释放空间 for(int i=0;i<rows;i++) delete []a2[i]; delete []a2;
利用vector创建二维数组
vector<vector<int> > a3(rows,vector<int>(columns)); for(int i=0;i<rows;i++){//初始化 for(int j=0;j<columns;j++){ a3[i][j] = a1[i][j]; } }
原文链接: https://www.cnblogs.com/BoysCryToo/p/13335212.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/368106
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
