经典算法面试题：交错字符串

今天的题目是个人非常喜欢的一个，题目的名字叫做“Interleaving String”，这个题目是什么意思呢？

理解题意

Interleaving 从字面上讲是交错交叉的意思，给定两个字符串s1:"a"和s2:"b"，那么对于s3:"ab"我们说s3是s1和s2“交错”形成的一个字符串，也就是说对于s3中的一个字符，这个字符要么来自于s1要么来自于s3且s1和s2中的字符只能使用一次。

因此对于s1 = "ab", s2 = "cd", s3 = "acbd"，我们可以说s3可以由s1和s2交错形成，过程是这样的：

• 使用s1的字符a

• 使用s2的字符c

• 使用s1的字符b

• 使用s2的字符d

这样就形成了s3：“acdb"

而对于s1 = "ab", s2 = "cd", s3 = "adbc"我们说s3不可以由s1和s2交错形成，原因很简单，过程是这样的：

• s3的第一个字符是a，因此必须使用s1的第一个字符a

• s3的第二个字符是d，但是此时可以用的s1的字符是b以及s2的字符c，无论选择s1亦或是选择s2都不能形成字符d，因此s3不可以由s1和s2交错形成

理解了题意后你能想到该怎么解决这个问题吗？

解决方法一：最简单解法

通常我们说在面试时针对算法题如果一下想不到最优解可以首先想一个最简单的时间复杂度较高的解法，那么对于这个问题来说最简单的解法是什么呢？

首先我们要意识到，这个问题的本质其实是一个“组合”问题，因为字符串s3是由s1和s2合并形成的，因此我们可以把s1和s2通过“交错”这种方式能形成的所有字符串组合出来然后看看s3是不是在这些字符串组合中。

对于s1：“ab”，s2：“cd”来说，我们首先把s1的字符a放到s2中，a可以放到s2的开头、末尾以及c和d的中间，因此形成了{acd，cad，cda}。

然后我们需要把s1的b放到上述中间结果中，我们只需要注意一点，那就是b一定要放到a的后面，因此对于中间结果中的acd来说，添加b之后形成的最后结果为{abcd, acbd, acdb}。

这样我们就把s1和s2能形成的所有结果都组合出来了，然后再看一下s3是不是在这些结果中就可以了。

这种解法相对简单，不足的地方在于组合过程中需要大量的字符串拼接，同时保留中间结果也占用内存，那么有没有更好的办法吗？

解决方法二：动态规划

希望大家不要一看到动态规划这几个字就不想接着往下看了，动态规划的思想非常简单，那就是“站在巨人的肩膀上”，当然在这里的巨人其实指的就是利用之前的计算结果不做重复计算。

让我们再仔细的看一下这个题目，s3字符串是由s1和s2形成的，对于s3中的一个字符要么来自s1要么来自s2，这对我们来说有什么启示呢？ 通过下图你就明白了：

对于s1:"ab", s2:"ac", s3:"aabc"来说，s3的第一个字符a既可以来自于s1也可以来自于s2，只有两种选择，无论选择哪一个我们都会得到一个新的子问题，因此我们需要进一步求解这个子问题，在这里我们使用f(i,j)来表示以s1的第i个位置到末尾形成的字符串和s2的第j个位置到末尾形成的字符串能否组合出s3从i+j到末尾形成的字符串。

有了这样的定义，那么我们知道如果s1[i]和s3[i+j]相同的话，那么我们就得到了一个新的子问题f(i+1, j)，如果我们知道f(i+1, j)的解那么我们当然就能知道f(i, j)，即：

f(i, j) = f(i+1, j)   if s1[i] == s3[i+j]

同样的道理如果s2[j]与s3[i+j]相同的话，那么我们知道：

f(i, j) = f(i, j+1)   if s2[j] == s3[i+j]

最终我们需要求解的是f(0, 0)，对此你应该很清楚了吧，这不就是初中数学的递归么，由子问题的解推导出当前问题的解，这就是动态规划。

有了这样的分析，代码就很简单了。

代码实现

bool isInterleave(string s1, string s2, string s3) {    int len1 = s1.length();    int len2 = s2.length();    int len3 = s3.length();
    if (len1 + len2 != len3)        return false;    if (s1 == "")        return s2 == s3;    if (s2 == "")        return s1 == s3;
    vector<vector<bool>> dp(len1+1, vector<bool>(len2+1, false));    dp[len1][len2] = true;    for(int i=len1-1;i>=0;i--)        dp[i][len2] = s1[i] == s3[i + len3-len1] && dp[i+1][len2];    for(int j=len2-1;j>=0;j--)        dp[len1][j] = s2[j] == s3[j + len3-len2] && dp[len1][j+1];
    for(int i=len1-1;i>=0;i--)        for (int j=len2-1;j>=0;j--)            dp[i][j] = s1[i] == s3[i+j] && dp[i+1][j] ||                        s2[j] == s3[i+j] && dp[i][j+1];    return dp[0][0];}

这里仅仅就是将上面的递归表达式翻译成代码而已，该算法的时间复杂度为O(s1.length * s2.length)。

总结

这个算法之所以很好是因为你可以使用多种方法来解决，解决问题即是一门技术也是一门艺术，你可以不知道最优解，但是你一定要让面试官看到你解决问题的能力，解决问题的能力才是面试官最看重的，而不是那个时间复杂度很低的"标准答案"。对于这个问题如果你有更好的解法欢迎在公众号留言。

为你推荐