首页 > 代码库 > [Leetcode] Interleaving String
[Leetcode] 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.
Solution 1: 指针的做法。。。错误！
比如例子： 在这种情况下，既可以进入s1，又可以进入s2，到底该进哪个呢，不能定。
| Input: | "aa", "ab", "abaa" |
| Output: | false |
| Expected: | true |
1 public class Solution { 2 public boolean isInterleave(String s1, String s2, String s3) { 3 if(s1==null||s1.length()==0) 4 return s2.equals(s3); 5 if(s2==null||s2.length()==0) 6 return s1.equals(s3); 7 int l1=s1.length(); 8 int l2=s2.length(); 9 int l3=s3.length();10 if(l3!=(l1+l2))11 return false;12 int index1=0;13 int index2=0;14 int index3=0;15 while(index1<l1&&index2<l2){16 if(s1.charAt(index1)==s3.charAt(index3)){17 index1++;18 index3++;19 }else if(s2.charAt(index2)==s3.charAt(index3)){20 index2++;21 index3++;22 }else{23 return false;24 }25 }26 return true;27 }28 }
Solution 2: DP.
http://www.cnblogs.com/springfor/p/3896159.html
“When you see string problem that is about subsequence or matching, dynamic programming method should come to your mind naturally. ”
所以这道题还是用DP的思想解决。
大体思路是，s1取一部分s2取一部分，最后是否能匹配s3。
动态规划数组是dp[i][j]，表示：s1取前i位，s2取前j位，是否能组成s3的前i+j位。
初始化是，假设s1为空，那么s2每一位跟s3匹配放入dp[0][j]；假设s2为空，那么s1每一位跟s3匹配放入dp[i][0]。
下面就继续匹配。讲解引用自： http://blog.csdn.net/u011095253/article/details/9248073
“
那什么时候取True，什么时候取False呢？
False很直观，如果不等就是False了嘛。
那True呢？首先第一个条件，新添加的字符，要等于s3里面对应的位( i + j 位)，第二个条件，之前那个格子也要等于True
举个简单的例子s1 = ab, s2 = c, s3 = bbc ，假设s1已经取了2位，c还没取，此时是False（ab!=bb），我们取s2的新的一位c，即便和s3中的c相等，但是之前是False，所以这一位也是False
同理，如果s1 = ab, s2 = c, s3=abc ，同样的假设，s1取了2位，c还没取，此时是True（ab==ab），我们取s2的新的一位c,和s3中的c相等，且之前这一位就是True，此时我们可以放心置True （abc==abc）
1 public class Solution { 2 public boolean isInterleave(String s1, String s2, String s3) { 3 if (s1 == null || s1.length() == 0) 4 return s2.equals(s3); 5 if (s2 == null || s2.length() == 0) 6 return s1.equals(s3); 7 int l1 = s1.length(); 8 int l2 = s2.length(); 9 int l3 = s3.length();10 if (l3 != (l1 + l2))11 return false;12 boolean[][] state = new boolean[l1 + 1][l2 + 1];13 state[0][0]=true;14 for(int i=1;i<=l1;++i){15 state[i][0]=state[i-1][0]&&(s1.charAt(i-1)==s3.charAt(i-1));16 }17 for(int i=1;i<=l2;++i){18 state[0][i]=state[0][i-1]&&(s2.charAt(i-1)==s3.charAt(i-1));19 }20 for(int i=1;i<=l1;++i){21 for(int j=1;j<=l2;++j){22 state[i][j]=(state[i][j-1]&&(s2.charAt(j-1)==s3.charAt(i+j-1)))||(state[i-1][j]&&(s1.charAt(i-1)==s3.charAt(i+j-1)));23 }24 }25 return state[l1][l2];26 }27 }
[Leetcode] Interleaving String