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.
A:
------------------3rd pass -----------------rolling table --------------------------------------
下面这个, 是不对的。 为了节省效率,我们就用了else if 来区别是s2 match最后一个还是s1 match最后一个。但是,这样是不对的。我的本意是对 blnArr[j] 判断,是否是true。public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int n1 = s1.length();
int n2 = s2.length();
int n3 = s3.length();
if( n1 + n2 != n3)
return false;
boolean blnArr[] = new boolean[n1+1];
blnArr[0] = true;
// if no s2 is used
for(int j =1; j<= n1;j++)
if(s1.charAt(j-1) == s3.charAt(j-1))
blnArr[j] = blnArr[j-1];
for(int i =0;i<n2;i++){// for each char in S2
for(int j =0; j<= n1;j++){ // iterate all the matching in s1
boolean isLastMatch = blnArr[j];
// if s2 ending the match
blnArr[j] = false;
if( s2.charAt(i) == s3.charAt( i+j ) ){
blnArr[j] = isLastMatch;
}else if(blnArr[j] == false && j>0 && s1.charAt(j-1) == s3.charAt(i+j) ){
//Now last char of s1, match the corresponding last char of s3
blnArr[j] = blnArr[j-1];
}
}
}
return blnArr[n1];
}
}
更改后的代码:
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { int n1 = s1.length(); int n2 = s2.length(); int n3 = s3.length(); if( n1 + n2 != n3) return false; boolean blnArr[] = new boolean[n1+1]; blnArr[0] = true; // if no s2 is used for(int j =1; j<= n1;j++) if(s1.charAt(j-1) == s3.charAt(j-1)) blnArr[j] = blnArr[j-1]; for(int i =0;i<n2;i++){// for each char in S2 for(int j =0; j<= n1;j++){ // iterate all the matching in s1 boolean isLastMatch = blnArr[j]; // if s2 ending the match blnArr[j] = false; if( s2.charAt(i) == s3.charAt( i+j ) ){ blnArr[j] = isLastMatch; } if( j>0 && s1.charAt(j-1) == s3.charAt(i+j) ){ //Now last char of s1, match the corresponding last char of s3 blnArr[j] |= blnArr[j-1]; } } } return blnArr[n1]; } }
above codes is simply for better understanding. actually ,we can combine the first for loop into the nested for loops(2 for loop) , then, we get the solution 4.
-----------------------------------------------1st pass ----------------------------
整个代码如下:
public class InterleavingString { public boolean isInterleave(String s1, String s2, String s3) { int n1 = s1.length(); int n2 = s2.length(); int n3 = s3.length(); if (n3 != n1 + n2) return false; return inInterleave(s1, 0, s2, 0, s3, 0); } private boolean inInterleave(String s1, int charS1, String s2, int charS2, String s3, int charS3) { if (charS3 == s3.length()-1 ){ if(charS1 == s1.length() && charS2 == s2.length() -1 && s2.charAt(charS2)==s3.charAt(charS3)){ return true; } if(charS1 == s1.length()-1 && charS2 == s2.length() && s1.charAt(charS1)==s3.charAt(charS3)){ return true; } return false; }else if (charS1 >= s1.length() || charS2 >= s2.length()) { return false; } boolean blnCase1 = false, blnCase2 = false; if (s1.charAt(charS1) == s3.charAt(charS3)) { blnCase1 = inInterleave(s1, charS1 + 1, s2, charS2, s3, charS3 + 1); } if (s2.charAt(charS2) == s3.charAt(charS3)) { blnCase2 = inInterleave(s1, charS1, s2, charS2 + 1, s3, charS3 + 1); } return blnCase1 || blnCase2; } }
但是,Recursion的 复杂度太高, 继续优化,就是 对s3的每个length,记录下 要组成它的所有的s1,s2的ending index的值。 但其实,这是不必要的。在计算i 位置的时候,只需要记住 i -1 位置。 并且,这里,我们用了Itnerval 的start 来代表 s1 的位置,end来记录s2的位置。
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { if (s1.length() + s2.length() != s3.length()) return false; if(s1.isEmpty()){ return s2.equals(s3); } if(s2.isEmpty()){ return s1.equals(s3); } // using Interval to record the ending position of s1 and s2 // Interval.start == ending of s1 // Interval.end == ending of s2 // check the first, to make the oneStepBack list not empty // position match list, for s3 at i-1 ArrayList<Interval> oneStepBack = new ArrayList<Interval>(); if (s1.charAt(0) == s3.charAt(0)) { oneStepBack.add(new Interval(0, -1)); } if (s2.charAt(0) == s3.charAt(0)) { oneStepBack.add(new Interval(-1, 0)); } if (oneStepBack.isEmpty()) { return false; } ArrayList<Interval> al; // new for (int i = 1; i < s3.length(); i++) { al = new ArrayList<Interval>();// record position at i while (!oneStepBack.isEmpty()) { Interval tmp = oneStepBack.remove(0); int lastS1 = tmp.start; int lastS2 = tmp.end; if (lastS1 + 1 < s1.length() && s1.charAt(lastS1 + 1) == s3.charAt(i)) { al.add(new Interval(lastS1 + 1, lastS2)); } if (lastS2 + 1 < s2.length() && s2.charAt(lastS2 + 1) == s3.charAt(i)) { al.add(new Interval(lastS1, lastS2 + 1)); } } if (al.isEmpty()) {// no match found at position i return false; } oneStepBack = al; } return true; } }---------但还是太慢------- 因为,只不过是把递归变成了循环调用,复杂度上没有什么变化
究其原因,在于如果S1,S2相同的情况太多的话,会导致重复利用。
因此,我们这里就有了Dynamic Programming的思路,建立一个2D array来记录。
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { int n1 = s1.length(), n2 = s2.length(), n3 = s3.length(); if (n1 + n2 != n3) return false; if (n1 == 0) return s2.equals(s3); if (n2 == 0) return s1.equals(s3); // create 2D array to store the matching case boolean[][] A = new boolean[n1 + 1][n2 + 1]; A[0][0] = true; // set up the boarder case for (int i = 1; i <= n1; i++) { // when s2 is empty A[i][0] = s1.charAt(i - 1) == s3.charAt(i - 1); } for (int j = 1; j <= n2; j++) { A[0][j] = s2.charAt(j - 1) == s3.charAt(j - 1); } // do the matching test char ch1, ch2, ch3; for (int i = 1; i <= n1; i++) { ch1 = s1.charAt(i - 1); for (int j = 1; j <= n2; j++) { ch2 = s2.charAt(j - 1); ch3 = s3.charAt(i + j - 1); A[i][j] = (A[i][j - 1] && (ch2 == ch3)) || (A[i - 1][j] && (ch1 == ch3)); } } return A[n1][n2]; } }
方法4:
更进一步的解法是: 只用一个1Darray,来记录s2的匹配情况。
如下面的代码:(每次呢,加入一个s2的character的时候,向左查看(有可能不能向左走了) 或者向上查看。 向左的时候,就用刚计算的值,向上的时候,就用上面该位置上次计算出的值。)
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { int n1 = s1.length(); int n2 = s2.length(); if(n1+n2 != s3.length()) return false; boolean[] A = new boolean[n1+1]; A[0]= true; for(int i =1;i<=n1; i++) // check s1 with s3, not using s2 A[i] = A[i-1] && s1.charAt(i-1) == s3.charAt(i-1); for(int i2 =0;i2< n2;i2++){// adding each char of s2 char ch2 = s2.charAt(i2); for(int i1 =0;i1<=n1;i1++){// for each length used in s1 char ch3 = s3.charAt(i1+i2); if(i1==0){ // if s1 is not used in s3 A[i1] &= ch2 == ch3; // no need to go left, go up only }else{ char ch1 = s1.charAt(i1-1); A[i1] = (A[i1-1] && ch1 == ch3) || (A[i1] && ch2 == ch3); // go left || go up } } } return A[n1]; } }
Mistakes:
1: 仅仅这样定义初始情况是不行的。
if (charS3 == s3.length() && charS1 == s1.length() && charS2 == s2.length()) {
return true;
}else if (charS1 > s1.length() || charS2 > s2.length()) {
return false;
}
会有一个越界的情况。 最终返回都是false
我们需要自己去check最后一个字母的情况。
if (charS3 == s3.length()-1 ){ if(charS1 == s1.length() && charS2 == s2.length() -1 && s2.charAt(charS2)==s3.charAt(charS3)){ return true; } if(charS1 == s1.length()-1 && charS2 == s2.length() && s1.charAt(charS1)==s3.charAt(charS3)){ return true; } return false; }else if (charS1 >= s1.length() || charS2 >= s2.length()) { return false; }2: 因为我们直接调用了s1,s2的第一个位置。可是,没有检查其一是否为空的情况。
3 : 忘记检查 输入的string,是否是empty, 直接就用开始取0位置的值了--->null pointer exception
4: check al.isEmpty()应该是在while loop 的外边。
5: 方法3中,建立2D数组的时候, 开始设置的大小是[n1+1][n2+1],但这样,会导致最终计算s3的位置的时候, i+j-2会导致,一直找不到最后的位置。
Learned:
1: leetcode中,不能自己建类的。 因此,我们开始,用了
class S1S2Index {} 会导致错误。--------------》 因此,用两个list 分别存储s1 s2 的index。
--------------第二遍,刚开始,是利用了2D matrix的方法-------------------
但是,是根据固定的s3的长度, 从0到s3.length(). ,并对每一个长度, 遍历其所有的s1,s2的可能情况。
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { int n1 = s1.length(), n2 = s2.length(), n3 = s3.length(); if (n1 + n2 != n3) return false; // 2D array, with [n1+1 n2+1] for which, it can be matched // indicating that A[i,j] could interleaving s3(i+j) // A[i,j] represent first i length of s1 , and first j length of s2, // if could representing i+j lenggh of s3, A[i,j] == true boolean[][] A = new boolean[n1 + 1][n2 + 1]; A[0][0] = true; // set first column for(int i = 1;i<=n1;i++) A[i][0] = A[i-1][0]&& s3.charAt(i-1)==s1.charAt(i-1); // set first column for(int j = 1;j<=n2;j++) A[0][j] = A[0][j-1] && s3.charAt(j-1)==s2.charAt(j-1); for (int l3 = 1; l3 <= n3; l3++) // l3 is the length of n3, not index for (int l1 = 1; l1 <= Math.min(n1, l3); l1++) { // all possible lenght of s1, l1 and l2 is at least 1 int l2 = l3 - l1; if(l2 <= 0 || l2>n2) continue; boolean matchAtS1 = s3.charAt(l3 - 1) == s1.charAt(l1 - 1) && A[l1 - 1][l2]; boolean matChAtS2 = s3.charAt(l3 - 1) == s2.charAt(l2 - 1) && A[l1][l2 - 1]; if (matchAtS1 || matChAtS2) { A[l1][l2] = true; } } return A[n1 ][n2 ]; } }
Mistakes: for 2D 的implementation:
1: 很郁闷,竟然最后,返回了 return A[n1+1][n2+1]这样SB的错误, 哎, 丢死人了
2: 由于对于所有s3的长度, 对于s1的长度不能任意取了。所以要检查l2的长度。否则~~~~
3: 对一个 l3, 当找到一个l1,l2来match 之后,不能break,要继续找到其他的match情况。
------------1D 的想法,自己的貌似不太行, 还是看上面的吧 ----
-----------自己的想法,就是每个位置,记录其能最远在s3中达到的距离。-
No comments:
Post a Comment