Interleaving String !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 就是用rolling table

Q:
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中达到的距离。-