Leetcode---Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

我们先研究一下这个问题，判断一个字符串s3是否由给定的字符串s1和s2交错而成：

由于s1和s2中可能有相同的字符，所以无法通过遍历s3得出结论。

那看一下是否有最优子结构？也就是说，问题的解是否可以由子问题的解推导出来。

假设s3的长度为l3，首先想到的是result[l3]=result[l3-1]&&(s3[l3-1]在s1或s2中)；

后来想想这个是必要条件，而状态方程需要是充分必要条件，于是假设s1长度l1，s2长度l2，那么

result(l1,l2)=result(l1-1,l2)&&s1[l1-1]==s3[l1+l2-1] || result(l1,l2-1)&&s2[l2-1]==s3[l1+l2-1]

以上是l1>0和l2>0的情况，当l1==0,l2>0时

result(0,l2)=result(0,l2-1)&&s2[l2-1]==s3[l2-1]

当l1>0,l2==0时

result(l1,0)=result(l1-1,0)&&s1[l1-1]==s3[l1-1]

当l1==0且l2==0时，

假设result(0,0)=true，以便上面的等式可以成立。

所以得到一个很简练的程序（DP的程序一向简练，关键是写对状态方程）：

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