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.

原问题链接：https://leetcode.com/problems/interleaving-string/

 

问题分析

　　这个问题有一点复杂，主要在于要理清楚里面比较复杂的关系。在这里对于两个给定的字符串s1和s2来说，需要轮流从两个串里取一部分字符串作为合并后的串的一部分。因此，从通常的角度来看，必然是首先从一个串里取一截加入到合并的串里。那么具体该取哪个串呢？如果是从串的最开头，那么我们可以既取s1也取s2。而在中间的某个部分的时候，我们则需要交替的取了。

　　因此，为了解决这个问题，我们有两种思路来解决。

 

递归法

　　 在开始的讨论里，我们已经看到，对于比较字段的匹配，我们可以是先取s1和目标串进行比较匹配，也可以开始是取s2来进行匹配。一旦某一个选定之后，我们就只能依次的选取后面的进行匹配了。所以假设在某个时候s1的当前位置是l1, s2的当前位置是l2, s3的当前位置是l3。那么我们就需要有一个元素来标识当前是已经匹配了哪个串的，到底是s1还是s2。这样就可以选择对应的串来和s3比较。

　　假定我们已经选定了某个串了，那么就要对它和s3进行比较。这个比较是满足什么样的关系呢？首先一个肯定是当前的字段要匹配。也就是说，假设当前s1位置是l1, s3的位置是l3，那么必然从l1到s1的末尾以及l3到s3的某位有一段是匹配的，可以匹配有１个或者多个元素。如果一个都不匹配，那么就应该返回false。

　　按照这个思路，我们得到如下的代码：

 

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length() + s2.length() != s3.length()) return false;
        return isInterleave(s1, 0, s2, 0, s3, 0, true) || isInterleave(s1, 0, s2, 0, s3, 0, false);
    }
    
    public boolean isInterleave(String s1, int l1, String s2, int l2, String s3, int l3, boolean selected) {
        if(l1 == s1.length()) return s2.substring(l2).equals(s3.substring(l3));
        if(l2 == s2.length()) return s1.substring(l1).equals(s3.substring(l3));
        if(selected) {
            for(int i = 0; i < s1.length() - l1 && s1.charAt(l1 + i) == s3.charAt(l3 + i); i++) {
                if(isInterleave(s1, l1 + i + 1, s2, l2, s3, l3 + i + 1, false)) return true;
            }
        } else {
            for(int i = 0; i < s2.length() - l2 && s2.charAt(l2 + i) == s3.charAt(l3 + i); i++) {
                if(isInterleave(s1, l1, s2, l2 + i + 1, s3, l3 + i + 1, true)) return true;
            }
        }
        return false;
    }
}

　　这种递归实现的方式效率并不高，因为它需要针对里面匹配的每个情况进行递归的看，其时间复杂度在极端情况下达到了O(2 ** n)。 所以在实际中运行的时候会导致超时的错误。

　　所以，这种办法虽然逻辑上正确，但是效率需要改进。 

 

动态规划法

　　在前面递归方法的基础上，我们会很自然的想到要用动态规划这个办法来改进效率。在具体的实现里，我们定义一个boolean[m + 1][n + 1]的矩阵。其中m, n分别表示s1, s2的长度。这样矩阵里boolean[i][j]则分别表示当s1里i位置和s2里j位置时对应s3里i + j位置的匹配情况。

　　在i == 0或者j == 0的情况下，相当于单独的s1或者s2和s3进行比较匹配的情况。所以从递归的关系来说matrix[i][j] = matrix[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)　或者

matrix[i][j] = matrix[i- 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)。

　　而对于其他的情况呢，则是这两种情况取或的关系。最终结果是返回matrix[m][n]。

　　根据上述讨论，详细的实现如下： 

 

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s3.length() != s1.length() + s2.length()) return false;
        int m = s1.length(), n = s2.length();
        boolean[][] matrix = new boolean[m + 1][n + 1];
        for(int i = 0; i <= m; i++)
            for(int j = 0; j <= n; j++) {
                if(i == 0 && j == 0) matrix[i][j] = true;
                else if(i == 0) matrix[i][j] = matrix[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
                else if(j == 0) matrix[i][j] = matrix[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
                else
                    matrix[i][j] = (matrix[i][j-1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)) ||
                        (matrix[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1));
            }
        return matrix[m][n];
    }
}