leetcode日记（84）交错字符串

很明显的动态规划，就是怎么用想了一段时间。（开始还怀疑过是不是双指针，发现不行，因为会出现s3的下一个字符同时能够匹配到两个字符串字符的情况）

然后就是构建数组dp[101][101]，数组代表前x个s1字符和前y个s2字符是否与前x+y个s3是交错字符串。

不断递归就行了：

class Solution {
public:string s1,s2,s3;int dp[101][101];bool dg(int x,int y){if(s1.size()==x&&s2.size()==y){dp[x][y]=1;return 1;}if(dp[x][y]!=-1) return dp[x][y]==1;bool b=0;if(s1.size()>x&&s1[x]==s3[x+y]){b=b|dg(x+1,y);}if(s2.size()>y&&s2[y]==s3[x+y]){b=b|dg(x,y+1);}dp[x][y]=b;return b;}bool isInterleave(string s1, string s2, string s3) {if(s1.size()+s2.size()!=s3.size()) return 0;this->s1=s1;this->s2=s2;this->s3=s3;memset(dp,-1,sizeof(dp));dg(0,0);return dp[s1.size()][s2.size()]==1;}
};

学到了一点东西就是可以用-1、0、1三种状态分别代表未判断、不是交错字符串、是交错字符串，之前也用到过这种做法，可以降低复杂度。