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 public class Solution {
 2     public boolean isInterleave(String s1, String s2, String s3) {
 3         int length_s1 = s1.length();
 4         int length_s2 = s2.length();
 5         int length_s3 = s3.length();
 6         if(length_s1 + length_s2 != length_s3)
 7             return false;
 8         boolean state[][] = new boolean[length_s1 + 1][length_s2 + 1];
 9         //init state[][]
10         state[0][0] = true;
11         for(int i = 1; i <= length_s1; i++){
12             state[i][0] = (s1.charAt(i - 1) == s3.charAt(i - 1)) && state[i - 1][0];
13         }//for
14         for(int i = 1; i <= length_s2; i++){
15             state[0][i] = (s2.charAt(i - 1) == s3.charAt(i - 1)) && state[0][i - 1];
16         }//for
17         
18         //fill state[][]
19         for(int i = 1; i <= length_s1; i++){
20             for(int j = 1; j <= length_s2; j++){                
21                 state[i][j] = (state[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (state[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
22             }//for
23         }//for
24         //Util.showTwoDimensionalArray(state);
25         return state[length_s1][length_s2];
26     }
27 }

思路

这是一道二维动态规划的题

参考：http://blog.csdn.net/sunbaigui/article/details/8980830

这里state[i][j]表示s3(1..i + j )个字符是否能由s1(1, i)和s2（1， j）个字符串组成

递推公式

state[i][j] = (state[i - 1][j] &&　s1.charAt(i - 1) )|| (state[i][j - 1] && s2.charAt(j - 1))

如果用递归会出现超时的问题