[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.

算法思路：

思路1：递归。很典型的递归。但是不用试，肯定超时；

思路2：DP。dp[i][j]表示s1[0~i]&s2[0~j]组成的串串，是否能组成s3[0,i+j]。

初始状态：

dp[0][i] 和 dp[i][0]，即单个字符串尽最大努力能匹配到什么程度。

余下的状态转移方程：

dp[i][j] = dp[i - 1][j] | dp[i][j - 1]　　　　 s1.charAt(i - 1) == s3.charAt(i + j - 1) == s2.charAt(j - 1) （第一次做木有考虑到这种情况）
dp[i][j] = dp[i - 1][j]　　　　　　　　　　 s1.charAt(i - 1) == s3.charAt(i + j - 1);
dp[i][j] = dp[i][j - 1]　　　　　　　　　　 s2.charAt(j - 1) == s3.charAt(i + j - 1);

代码如下：

 1 public class Solution {
 2     public boolean isInterleave(String s1, String s2, String s3) {
 3         if(s1.length() == 0) return s2.equals(s3);
 4         if(s2.length() == 0) return s1.equals(s3);
 5         if(s1.length() + s2.length() != s3.length()) return false;
 6         int height = s1.length();
 7         int width = s2.length();
 8         boolean[][] dp = new boolean[height + 1][width + 1];
 9         dp[0][0] = true;
10         for(int i = 1; i <= height; i++)
11             if(s1.substring(0,i).equals(s3.substring(0,i))) dp[i][0] = true;
12         for(int i = 1; i <= width; i++)
13             if(s2.substring(0,i).equals(s3.substring(0,i))) dp[0][i] = true;
14         for(int i = 1; i <= height; i++){
15             for(int j = 1; j <= width; j++){
16                 char c1 = s1.charAt(i - 1), c2 = s2.charAt(j - 1), c3 = s3.charAt(i + j - 1);
17                 if(c1 == c3 && c2 == c3){
18                     dp[i][j] = dp[i - 1][j] | dp[i][j - 1];
19                 }else if(c1 == c3 ){
20                     dp[i][j] = dp[i - 1][j];
21                 }else if(c2 == c3){
22                     dp[i][j] = dp[i][j - 1];
23                 }
24             }
25         }
26         return dp[height][width];
27     }
28 }

代码好粗啊。。。。