Leetcode 97交错字符

用动态规划的思路比较简单

    // 假设dp[i][j]表示s1的前i个字母和s2的前j的字母，可以交错为s3的前i+j个字母

    // dp[i-1][j]表示s1的前i-1个字母和s2的前j个字母，可以交错为s3的前i+j-1个字母

    // dp[i][j] = (dp[i-1][j] && s1[i] == s3[i+j]) || (dp[i][j-1] && s2[j] == s3[i+j])

还是需要注意字符串的边界处理。
 

1class Solution {
2public:
3    // 假设dp[i][j]表示s1的前i个字母和s2的前j的字母，可以交错为s3的前i+j个字母
4    // dp[i-1][j]表示s1的前i-1个字母和s2的前j个字母，可以交错为s3的前i+j-1个字母
5    // dp[i][j] = (dp[i-1][j] && s1[i] == s3[i+j]) || (dp[i][j-1] && s2[j] == s3[i+j])
6    bool isInterleave(string s1, string s2, string s3) {
7        int n = s1.size(), m = s2.size();
8        if(n+m!=s3.size()) return false;
9        s1 = " "+s1, s2 = " "+s2, s3 = " "+s3;
10        vector<vector<bool>> dp(n+1,vector<bool>(m+1,false));
11        //dp[0][0] = true;
12        for(int i=0;i<=n;i++){
13            for(int j=0;j<=m;j++){
14                if(i==0&&j==0) dp[i][j] = true;
15                else if(i==0) dp[i][j] = dp[i][j-1] && s2[j]==s3[i+j];
16                else if(j==0) dp[i][j] = dp[i-1][j] && s1[i]==s3[i+j];
17                else dp[i][j] = (dp[i][j-1] && s2[j]==s3[i+j]) || (dp[i-1][j] && s1[i]==s3[i+j]);
18            }
19        }
20        return dp[n][m];
21    }
22};