给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出: true
示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 输出: false
注意题目，s3是由s1和s2交错组成，对比示例1和示例2可以知道，s1个字符的相对位置不能改变，s2也是。
此题用动态规划解，动态规划题手动画出个二维数组会比较容易理解。
1 class Solution { 2 public boolean isInterleave(String s1, String s2, String s3) { 3 int len1=s1.length(); 4 int len2=s2.length(); 5 int len3=s3.length(); 6 //若s3长度不等于s1加上s2的长度，就直接返回false 7 if(len1+len2!=len3) 8 return false; 9 //在此处判断是否有一方为空 10 if(s1.equals("")) return s2.equals(s3); 11 if(s2.equals("")) return s1.equals(s3); 12 //建立dp数组，dp[i][j]代表s1的前i个数和s2的前j个数合并起来能否构成s3的前i+j个数 13 boolean [][]dp=new boolean[len1+1][len2+1]; 14 //初始化dp数组 15 dp[0][0]=true; 16 for(int i=1;i<=len1;i++) 17 dp[i][0]=s3.charAt(i-1)==s1.charAt(i-1)&&dp[i-1][0]; 18 for(int j=1;j<=len2;j++) 19 dp[0][j]=s3.charAt(j-1)==s2.charAt(j-1)&&dp[0][j-1]; 20 21 for(int i=1;i<=len1;i++) 22 for(int j=1;j<=len2;j++){ 23 //构造二维数组后可得，dp[i][j]可由dp[i-1][j]添加s1的第i个数 24 //或由dp[i][j-1]添加s2的第j个数得到，此时两种情况，其中一个为true即可 25 //由此得到递推式 26 dp[i][j]=(dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1)) 27 ||(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1)); 28 } 29 return dp[len1][len2]; 30 } 31 }