题目

题解

首先就想的是动态规划法 用dp[i][j] ->即当s1取长度i s2取长度j时是否满足 需要注意的是当其中一个字符串为0 则另一个字符串必须全部与s3匹配才为1

int n1 = s1.size(), n2 = s2.size();
        vector<vector<bool>> dp(n1+1,vector<bool>(n2+1));
        dp[0][0] = true;
        for(int i=1;i<=n1;++i)
        {
            dp[i][0] = dp[i-1][0]&&(s1[i-1]==s3[i-1]);
        }
        for(int i=1;i<=n2;++i)
        {
            dp[0][i] = dp[0][i-1]&&(s2[i-1]==s3[i-1]);
        }
        for(int i=1;i<=n1;i++)
        {
            for(int j=1;j<=n2;j++)
            {
                dp[i][j] = dp[i-1][j]&&s1[i-1]==s3[i-1+j]||dp[i][j-1]&&s2[j-1]==s3[i-1+j];
            }
        }

 当然这是很容易想到的 动态规划 但是

进阶：您能否仅使用 O(s2.length) 额外的内存空间来解决它?

我们针对中心循环进行分析

 for(int i=1;i<=n1;i++)
        {
            for(int j=1;j<=n2;j++)
            {
                dp[i][j] = dp[i-1][j]&&s1[i-1]==s3[i-1+j]||dp[i][j-1]&&s2[j-1]==s3[i-1+j];
            }
        }

dp[i-1][j]意味着如果使用s1字符 那么之前的s1字符必须可行 同理dp[i][j-1]意味着如果这里使用s2字符 那么之前的s2字符必须可行

那么两个值是怎么来的呢 

dp[i-1][j]是来自当i=i-1时循环出来的 也就是上一层的循环

而dp[i][j-1]则是上一次循环得到的

我们发现 每一轮 层数最多只用到了他的上一层循环的值 而上两层之类的根本没用到!! 那么我们可以进行覆盖操作 只用一行容器 将新一轮的数据覆盖掉旧的数据 

然后 我们就使用dp[j] 去代表s2 就可以了 然后每一轮都覆盖一遍 dp[i-1][j]->dp[j] dp[i][j-1]->dp[j-1]

 for (int i = 1; i <= n1; i++) {
            for (int j = 0; j <= n2; j++) {
                //j=0时 意味着s2不取 只看s1是否和s3匹配
                //j!=0时 dp[j - 1] && s2[j - 1] == s3[i + j - 1]-> dp[j - 1]是上一次循环的结果即s2少一个字符 这里是否取s2的字符
                //dp[j] && s1[i - 1] == s3[i + j - 1] dp[j]是上一轮循环的结果即s1少一个字符 意思是这里是否取s1的字符
                dp[j] = j==0?  (dp[0] && s1[i - 1] == s3[i - 1]):
                      (dp[j - 1] && s2[j - 1] == s3[i + j - 1]) || (dp[j] && s1[i - 1] == s3[i + j - 1]);
            }
        }

代码

 1 #include<iostream>
 2 #include<string>
 3 #include<vector>
 4 using namespace std;
 5 class Solution {
 6 public:
 7     bool isInterleave(string s1, string s2, string s3) {
 8         if (s1.size() + s2.size() != s3.size()) {
 9             return false;
10         } 
11         int n1 = s1.size(), n2 = s2.size();
12         vector<bool> dp(vector<bool>(n2 + 1, false));
13         //s2为0时的情况
14         dp[0] = true;
15         //s1为0的情况 只看s2是否和s3匹配
16         for (int j = 1; j <= n2&& s2[j - 1] == s3[j - 1]; j++) {
17             dp[j] = true;
18         }
19         for (int i = 1; i <= n1; i++) {
20             for (int j = 0; j <= n2; j++) {
21                 //j=0时 意味着s2不取 只看s1是否和s3匹配
22                 //j!=0时 dp[j - 1] && s2[j - 1] == s3[i + j - 1]-> dp[j - 1]是上一次循环的结果即s2少一个字符 这里是否取s2的字符
23                 //dp[j] && s1[i - 1] == s3[i + j - 1] dp[j]是上一轮循环的结果即s1少一个字符 意思是这里是否取s1的字符
24                 dp[j] = j==0?  (dp[0] && s1[i - 1] == s3[i - 1]):
25                       (dp[j - 1] && s2[j - 1] == s3[i + j - 1]) || (dp[j] && s1[i - 1] == s3[i + j - 1]);
26             }
27         }
28         return dp[n2];
29     }
30 };
31 
32 int main() {
33     Solution sol;
34     string s1 = "aabcc"; 
35     string s2 = "dbbca";
36     string s3 = "aadbbcbcac";
37     bool result=sol.isInterleave(s1,s2,s3);
38     cout << result << endl;
39 
40 }