首页 > 代码库 > [Leetcode][JAVA] Interleaving String
[Leetcode][JAVA] 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.
使用DP, 过程如下图所示：
S2 | |||||||
S1 | aadbbcbcac | 0 “” | 1 d | 2 db | 3 dbb | 4 dbbc | 5 dbbca |
0 “” | T | F(d!=a) | F | F | F | F | |
1 a | T(a==a) | F(aa) | F | F | F | F | |
2 aa | T | T(aad) | T(aadb) |
|
|
| |
3 aab | F(aab!=aad) | T(aadb) | T(aadbb) |
|
|
| |
4 aabc | F | F(aadbb) | T(aadbbc) |
|
|
| |
5 aabcc | F | F(aadbbc) |
|
|
|
| |
发现某一格dp[i][j]为true只有当其上面或左边为true才行。且需要新加入的字母与s3新添加的字母一致，True状态才能延续。
代码：
1 public boolean isInterleave(String s1, String s2, String s3) { 2 int l1=s1.length(); 3 int l2=s2.length(); 4 int l3=s3.length(); 5 if(l1+l2!=l3) 6 return false; 7 boolean[][] dp = new boolean[l1+1][l2+1]; 8 for(int i=0;i<=l1;i++) { 9 for(int j=0;j<=l2;j++) {10 if(i==0 && j==0)11 dp[i][j]=true;12 else if(i==0)13 dp[i][j] = dp[i][j-1] && (s2.charAt(j-1)==s3.charAt(i+j-1));14 else if(j==0)15 dp[i][j] = dp[i-1][j] && (s1.charAt(i-1)==s3.charAt(i+j-1));16 else17 dp[i][j] = (dp[i][j-1] && (s2.charAt(j-1)==s3.charAt(i+j-1))) || (dp[i-1][j] && (s1.charAt(i-1)==s3.charAt(i+j-1)));18 }19 }20 return dp[l1][l2];21 }
简化为一维数组：
1 public boolean isInterleave(String s1, String s2, String s3) { 2 int l1 = s1.length(); 3 int l2 = s2.length(); 4 int l3 = s3.length(); 5 if(l3!=(l1+l2)) 6 return false; 7 boolean[] dp = new boolean[l2+1]; 8 dp[0] = true; 9 for(int i=1;i<dp.length;i++)10 {11 dp[i] = dp[i-1] && (s2.charAt(i-1)==s3.charAt(i-1));12 }13 for(int i=1;i<=l1;i++)14 {15 for(int j=0;j<dp.length;j++)16 {17 if(j==0)18 dp[j] = dp[j] && (s1.charAt(i-1)==s3.charAt(i-1));19 else20 dp[j] = (dp[j] && (s1.charAt(i-1)==s3.charAt(i+j-1))) || (dp[j-1] && (s2.charAt(j-1)==s3.charAt(i+j-1)));21 }22 }23 24 return dp[l2];25 }
[Leetcode][JAVA] Interleaving String
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。