判断字符串能否由另外两个字符串相交构成

"求是否存在"，毫无疑问，又是一道动态规划题。设当前子序列为S1[0..i],S2[0..j],S3[0..i+j+1]，dp[i+1][j+1]==true表示S3[0..i+j]可以由S1[0..i]和S2[0..j]交叉组成，得到如下状态推导公式：

1. 如果S1[i]==S3[i+j+1]&&S2[j]!=S3[i+j+1]，那么dp[i+1][j+1] = dp[i][j+1]
2. 如果S1[i]!=S3[i+j+1]&&S2[j]==S3[i+j+1]，那么dp[i+1][j+1] = dp[i+1][j][k+1]
3. 如果S1[i]==S3[i+j+1]&&S2[j]==S3[i+j+1]，那么dp[i+1][j+1] = dp[i][j+1]||dp[i+1][j]
4. 如果S1[i]!=S3[i+j+1]&&S2[j]!=S3[i+j+1]，那么dp[i+1][j+1] = false
5. 基准1: dp[0][0]=true
6. 基准2: dp[0][1..len2]和dp[1..len1][0]

注意：如果S1的最大下标为i，S2最大下标为j，那么合并S1和S2之后的最大下标为i+j+1

代码如下：

class Solution {
public:
    /**
     *
     * @param s1 string字符串
     * @param s2 string字符串
     * @param s3 string字符串
     * @return bool布尔型
     */
    bool isInterleave(string s1, string s2, string s3) {
        // write code here
        int a = s1.size(), b = s2.size(), c = s3.size();
        if (a + b != c) return false;
        vector<vector<bool> > dp(a+1, vector<bool>(b+1, false));
        dp[0][0] = true;
        for (int i = 0; i < a && s1[i] == s3[i]; ++i) dp[i+1][0] = true;
        for (int i = 0; i < b && s2[i] == s3[i]; ++i) dp[0][i+1] = true;
        for (int i = 0; i < a; ++i) {
            for (int j = 0; j < b; ++j) {
                int m = s1[i], n = s2[j], o = s3[i+j+1];
                if (m == o && n != o) dp[i+1][j+1] = dp[i][j+1];
                if (m != o && n == o) dp[i+1][j+1] = dp[i+1][j];
                if (m == o && n == o) dp[i+1][j+1] = dp[i][j+1] || dp[i+1][j];
                if (m != o && n != o) dp[i+1][j+1] = false;
            }
        }
        return dp[a][b];
    }
};