[leetcode_97]Interleaving String

给定串s1,s2，计算s3是否为s1和s2顺序叠加的串。
这个题开始模拟，但是有一个问题，如果s1[p1]和s2[p2]同时都等于s3[p3]怎么办，这个时候如果选择的话就需要预存状态然后开始搜索。
果然超时。
网上有人说用DP
f[i][j] = f[i-1][j] + s1[i] && s1[i] == s3[k]
f[i][j] = f[i][j-1](i+j = k) && s2[j] == s3[j]
s3串中的第k个字符完全匹配是需要s1串中的第i个字符或者s2串中的第j个字符相等才行。
枚举所有情况，最多n^2
输出f[i][j] i = s1.length() j = s2.length() i+j = s3.length()即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
public:
    bool ***f;
    bool isInterleave(string s1, string s2, string s3) {
        if(s1.length() + s2.length() != s3.length())return false;
        bool f[500][500];
        for(int i = 0;i < 500;i++) {
            for(int j = 0;j < 500;j++) {
                f[i][j] = false;
            }
        }
        f[0][0] = true;
        for(int i = 1;i <= s3.length();i++) {
            for(int j = 0;j < i;j++) {
                if(f[j][i-1-j] && i-1-j<=s2.length() && j+1 <= s1.length() && s1[j] == s3[i-1]) {
                    f[j+1][i-1-j] = true;
                }
                if(f[j][i-1-j] && j <= s1.length() && i-1-j+1 <= s2.length() && s2[i-1-j] == s3[i-1]) {
                    f[j][i-1-j+1] = true;
                }
            }
        }
        return f[s1.length()][s2.length()];
    }
};