097.Interleaving-String

这种可行性的问题，直觉就是DP。而且此题很明显，是否是s1,s2,s3是否满足交叉子串，必然取决于他们的上一级（少一个字符）状态是否满足交叉子串。

程序最开始，一个快速的判别条件是 n1+n2==n3，不满足的立即退出。

设置状态数组dp[i][j]，表示s1的前i个字符、s2的前j个字符、s3的前i+j个字符，是否满足交叉子串的关系。其中i=1,2,..,n1，j=1,2,..,n2

状态转移方程很容易写，我们先粗浅地写出来：

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

考虑边界条件。从上述的转移方程中可以发现需要提前设置dp[i][0](for all i)和dp[0][j](for all j)。

dp[i][0]表示从s1里取前i个，是否能与s3的前i个组成交叉子串。显然就是判断s1和s3是否逐位相等。这包含了另一个准动态规划小问题。

   for (int i=1; i<=n1; i++)
   {
       if (dp[i-1][0]==1 && s1[i]==s3[i])
          dp[i][0]=1;
   }

同理可以设置dp[0][j]。

注意到这两个小问题又都要涉及到边界条件dp[0][0]。这个条件需要dp[0][0]=1.

Leetcode Link