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.
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { if("".equals(s1)){ return s3.equals(s2); } if("".equals(s2)){ return s3.equals(s1); } if(s3.length()!=s1.length()+s2.length()){ return false; } char a1[]=s1.toCharArray(); char a2[]=s2.toCharArray(); char a3[]=s3.toCharArray(); boolean dp[][]=new boolean[s1.length()+1][s2.length()+1]; //dp[i][j]表示将s1[i-1]和s2[j-1]能否匹配s3 dp[0][0]=true; for(int i=1;i<s1.length()+1;i++){ dp[i][0]=dp[i-1][0]&(a1[i-1]==a3[i-1+0]); } for(int i=1;i<s2.length()+1;i++){ dp[0][i]=dp[0][i-1]&(a2[i-1]==a3[i-1+0]); } for(int i=1;i<s1.length()+1;i++){ for(int j=1;j<s2.length()+1;j++){ dp[i][j]=(dp[i-1][j]&(a1[i-1]==a3[i-1+j])) ||(dp[i][j-1]&&(a2[j-1]==a3[i-1+j])); } } return dp[s1.length()][s2.length()]; } }