leetcode97.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.

输入数组s1,s2和s3,判断s3是不是由s1和s2中的元素交替组成的。

思路一：backtracking

乍一看这题可以通过递归的方式来求解。我们可以同时判断当前下标s1和s2的元素是不是和s3当前下标的元素相同。如果相同，就进入下一轮递归。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
public boolean isInterleave(String s1, String s2, String s3) {
    if(s1.length() + s2.length() != s3.length()) return false;
    return isInterleave(s1, s2, s3, 0,0,0);
}

public boolean isInterleave(String s1, String s2, String s3, int pointer1, int pointer2, int pointer3){
    if(pointer1==s1.length() && pointer2==s2.length())return pointer3 == s3.length();
    if(pointer1<s1.length() && s1.charAt(pointer1)==s3.charAt(pointer3) && isInterleave(s1,s2,s3,pointer1+1, pointer2, pointer3+1)) return true;
    if(pointer2<s2.length() && s2.charAt(pointer2)==s3.charAt(pointer3) && isInterleave(s1,s2,s3,pointer1, pointer2+1, pointer3+1)) return true;
    return false;
}

这段代码 不出意外的 超时了

因为这里有太多的重复调用了。很多的判断在第一次递归的过程中就可以知道，数组在走到s1和s2中的某个位置pointer1，pointer2时会进入死胡同。而走到pointer1和pointer2对应的s3中的pointer3也是确定的。所以如果我们可以利用这部分信息，就可以省略掉很多重复的判断。这里我们利用boolean[][]数组记录判断情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean isInterleave2(String s1, String s2, String s3) {
    if(s1.length() + s2.length() != s3.length()) return false;
    return isInterleave(s1, s2, s3, 0,0,0, new boolean[s1.length()+1][s2.length()+1]);
    
}

public boolean isInterleave(String s1, String s2, String s3, int pointer1, int pointer2, int pointer3, boolean[][] isInvalid){
    if(isInvalid[pointer1][pointer2]) return false;
    if(pointer3 == s3.length())return true;
    boolean isValid = pointer1<s1.length() && s1.charAt(pointer1)==s3.charAt(pointer3) && isInterleave(s1,s2,s3,pointer1+1,pointer2, pointer3+1, isInvalid)
            || pointer2<s2.length() && s2.charAt(pointer2)==s3.charAt(pointer3) && isInterleave(s1,s2,s3,pointer1,pointer2+1,pointer3+1,isInvalid);
    if(!isValid) isInvalid[pointer1][pointer2]=true;
    return isValid;
}

dynamic programming

同样适用boolean[][]作为存储临时值的数据结构，这里我们将其代表的含义改变为至下标(i,j)时是否可以和前(i-1,j)或是(i,j-1)上的值连接满足s3。
解释如下：在这里(i,j)位置值的含义代表如果采用s2的前i个值和s1的前j个值，是否可以组成s3前i+j个值。所以判断(i,j)需要参考(i-1,j)和(i,j-1)位置上的值。如果(i-1,j)成立，也就是说s2的前i-1个值和s1的前j个值可以组成s3前i+j-1个值，那么如果s2的第i个值等于s3的第i+j个值，那么该式子成立。（i,j-1）也是同理的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isInterleave3(String s1, String s2, String s3){
    if ((s1.length()+s2.length())!=s3.length()) return false;
    boolean[][] matrix = new boolean[s2.length()+1][s1.length()+1];
    matrix[0][0] = true;
    for(int i = 1 ; i<s1.length()+1 ; i++){
        matrix[0][i] = matrix[0][i-1] && s1.charAt(i-1)==s3.charAt(i-1);
    }
    for(int i = 1 ; i<s2.length()+1 ; i++){
        matrix[i][0] = matrix[i-1][0] && s2.charAt(i-1)==s3.charAt(i-1);
    }
    
    for(int i = 1 ; i<matrix.length ; i++){
        for(int j = 1 ; j<matrix[0].length ; j++){
            matrix[i][j] = (matrix[i-1][j] && s2.charAt(i-1)==s3.charAt(i+j-1))
                    ||(matrix[i][j-1] && s1.charAt(j-1)==s3.charAt(i+j-1));
        }
    }
    return matrix[s2.length()][s1.length()];
}

最后的简化

在上一种思路中，我们可以看到，其实在每一层的遍历中只有上一层数据和前一个数据对当前数据有参考价值。所以我们可以将boolean[][]的二维数组简化为boolean[]一维数组的数据结构。提高空间的利用率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isInterleave4(String s1, String s2, String s3){
    if ((s1.length()+s2.length())!=s3.length()) return false;
    boolean[] matrix = new boolean[s2.length()+1];
    for(int i = 0 ; i<=s1.length() ; i++){
        for(int j = 0 ; j<=s2.length() ; j++){
            if(i==0&&j==0){
                matrix[j] = true;
            }else if(i==0){
                matrix[j] = matrix[j-1] && s2.charAt(j-1)==s3.charAt(j-1);
            }else if(j==0){
                matrix[j] = matrix[j] && s1.charAt(i-1) == s3.charAt(i-1);
            }else{
                matrix[j] = (matrix[j-1] && s2.charAt(j-1)==s3.charAt(i+j-1))
                        || (matrix[j] && s1.charAt(i-1)==s3.charAt(i+j-1));
            }
        }
    }
    return matrix[s2.length()];
}