给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac” 输出: true 示例 2:
输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc” 输出: false
思路： 1.状态为：dp[i][j]为s1前i个字符加上s2前j个字符能否组成s3前i+j个字符。 2.边界条件:
dp[0][0] = true; 因为空串s1和空串s2能组成空串s3。如果s3前i个字符能只由s1前i个字符组成，那么dp[i][0]=true;一旦有一个字符不能组成，那么后面的dp[i][0]都为false。dp[0][j]类似。dp[i][j]= 如果s1的前i-1个字符和s2的前j个字符能组成dp[i-1][j]并且s1[i]=s3[i+j]。 或者s2的前j-1个字符和s1的前i个字符能组成dp[i][j-1]并且s2[k]=s3[i+j]。 那么dp[i][j]=true。 public boolean isInterleave(String s1, String s2, String s3) { int l1 = s1.length(); int l2 = s2.length(); int l3 = s3.length(); if(l1+l2!=l3) return false; boolean[][] dp = new boolean[l1+1][l2+1]; dp[0][0] = true; for(int i=0;i<l1;i++) { if(s1.charAt(i)==s3.charAt(i)) dp[i+1][0] = true; else break; } for(int i=0;i<l2;i++) { if(s2.charAt(i)==s3.charAt(i)) dp[0][i+1] = true; else break； } for(int i=1;i<=l1;i++) for(int j=1;j<=l2;j++) { if((dp[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1)) || dp[i][j-1] && s2.charAt(j-1)==s3.charAt(i+j-1)) dp[i][j] = true; else dp[i][j] = false; } return dp[l1][l2]; }