Interleaving String

Question

  1. Given three strings: s1, s2, s3,
  2. determine whether s3 is formed by the interleaving of s1 and s2.
  4. Example
  5. For s1 = "aabcc", s2 = "dbbca"
  7. When s3 = "aadbbcbcac", return true.
  8. When s3 = "aadbbbaccc", return false.
  9. Challenge
  10. O(n2) time or better

题解1 - bug

题目意思是 s3 是否由 s1 和 s2 交叉构成，不允许跳着从 s1 和 s2 挑选字符。那么直觉上可以对三个字符串设置三个索引，首先从 s3 中依次取字符，然后进入内循环，依次从 s1 和 s2 中取首字符，若能匹配上则进入下一次循环，否则立即返回 false. 我们先看代码，再分析 bug 之处。

Java

  1. public class Solution {
  2.     /**
  3.      * Determine whether s3 is formed by interleaving of s1 and s2.
  4.      * @param s1, s2, s3: As description.
  5.      * @return: true or false.
  6.      */
  7.     public boolean isInterleave(String s1, String s2, String s3) {
  8.         int len1 = (s1 == null) ? 0 : s1.length();
  9.         int len2 = (s2 == null) ? 0 : s2.length();
  10.         int len3 = (s3 == null) ? 0 : s3.length();
  12.         if (len3 != len1 + len2) return false;
  14.         int i1 = 0, i2 = 0;
  15.         for (int i3 = 0; i3 < len3; i3++) {
  16.             boolean result = false;
  17.             if (i1 < len1 && s1.charAt(i1) == s3.charAt(i3)) {
  18.                 i1++;
  19.                 result = true;
  20.                 continue;
  21.             }
  22.             if (i2 < len2 && s2.charAt(i2) == s3.charAt(i3)) {
  23.                 i2++;
  24.                 result = true;
  25.                 continue;
  26.             }
  28.             // return instantly if both s1 and s2 can not pair with s3
  29.             if (!result) return false;
  30.         }
  32.         return true;
  33.     }
  34. }

源码分析

异常处理部分：首先求得 s1, s2, s3 的字符串长度，随后用索引 i1, i2, i3 巧妙地避开了繁琐的 null 检测。这段代码能过前面的一部分数据，但在 lintcode 的第15个 test 跪了。不想马上看以下分析的可以自己先 debug 下。

我们可以注意到以上代码还有一种情况并未考虑到，那就是当 s1[i1] 和 s2[i2] 均和 s3[i3] 相等时，我们可以拿 s1 或者 s2 去匹配，那么问题来了，由于不允许跳着取，那么可能出现在取了 s1 中的字符后，接下来的 s1 和 s2 首字符都无法和 s3 匹配到，因此原本应该返回 true 而现在返回 false. 建议将以上代码贴到 OJ 上看看测试用例。

以上 bug 可以通过加入对 (s1[i1] == s3[i3]) && (s2[i2] == s3[i3]) 这一特殊情形考虑，即分两种情况递归调用 isInterleave, 只不过 s1, s2, s3 为新生成的字符串。

复杂度分析

遍历一次 s3, 时间复杂度为 O(n), 空间复杂度 O(1).

题解2

在 (s1[i1] == s3[i3]) && (s2[i2] == s3[i3]) 时分两种情况考虑，即让 s1[i1] 和 s3[i3] 配对或者 s2[i2] 和 s3[i3] 配对，那么嵌套调用时新生成的字符串则分别为 s1[1+i1:], s2[i2], s3[1+i3:] 和 s1[i1:], s2[1+i2], s3[1+i3:]. 嵌套调用结束后立即返回最终结果，因为递归调用时整个结果已经知晓，不立即返回则有可能会产生错误结果，递归调用并未影响到调用处的 i1 和 i2.

Python

  1. class Solution:
  2.     """
  3.     @params s1, s2, s3: Three strings as description.
  4.     @return: return True if s3 is formed by the interleaving of
  5.              s1 and s2 or False if not.
  6.     @hint: you can use [[True] * m for i in range (n)] to allocate a n*m matrix.
  7.     """
  8.     def isInterleave(self, s1, s2, s3):
  9.         len1 = 0 if s1 is None else len(s1)
  10.         len2 = 0 if s2 is None else len(s2)
  11.         len3 = 0 if s3 is None else len(s3)
  13.         if len3 != len1 + len2:
  14.             return False
  16.         i1, i2 = 0, 0
  17.         for i3 in xrange(len(s3)):
  18.             result = False
  19.             if (i1 < len1 and s1[i1] == s3[i3]) and \
  20.                (i1 < len1 and s1[i1] == s3[i3]):
  21.                 # s1[1+i1:], s2[i2:], s3[1+i3:]
  22.                 case1 = self.isInterleave(s1[1 + i1:], s2[i2:], s3[1 + i3:])
  23.                 # s1[i1:], s2[1+i2:], s3[1+i3:]
  24.                 case2 = self.isInterleave(s1[i1:], s2[1 + i2:], s3[1 + i3:])
  25.                 return case1 or case2
  27.             if i1 < len1 and s1[i1] == s3[i3]:
  28.                 i1 += 1
  29.                 result = True
  30.                 continue
  32.             if i2 < len2 and s2[i2] == s3[i3]:
  33.                 i2 += 1
  34.                 result = True
  35.                 continue
  37.             # return instantly if both s1 and s2 can not pair with s3
  38.             if not result:
  39.                 return False
  41.         return True

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * Determine whether s3 is formed by interleaving of s1 and s2.
  5.      * @param s1, s2, s3: As description.
  6.      * @return: true of false.
  7.      */
  8.     bool isInterleave(string s1, string s2, string s3) {
  9.         int len1 = s1.size();
  10.         int len2 = s2.size();
  11.         int len3 = s3.size();
  13.         if (len3 != len1 + len2) return false;
  15.         int i1 = 0, i2 = 0;
  16.         for (int i3 = 0; i3 < len3; ++i3) {
  17.             bool result = false;
  18.             if (i1 < len1 && s1[i1] == s3[i3] &&
  19.                 i2 < len2 && s2[i2] == s3[i3]) {
  20.                 // s1[1+i1:], s2[i2:], s3[1+i3:]
  21.                 bool case1 = isInterleave(s1.substr(1 + i1), s2.substr(i2), s3.substr(1 + i3));
  22.                 // s1[i1:], s2[1+i2:], s3[1+i3:]
  23.                 bool case2 = isInterleave(s1.substr(i1), s2.substr(1 + i2), s3.substr(1 + i3));
  24.                 // return instantly
  25.                 return case1 || case2;
  26.             }
  28.             if (i1 < len1 && s1[i1] == s3[i3]) {
  29.                 i1++;
  30.                 result = true;
  31.                 continue;
  32.             }
  34.             if (i2 < len2 && s2[i2] == s3[i3]) {
  35.                 i2++;
  36.                 result = true;
  37.                 continue;
  38.             }
  40.             // return instantly if both s1 and s2 can not pair with s3
  41.             if (!result) return false;
  42.         }
  44.         return true;
  45.     }
  46. };

Java

  1. public class Solution {
  2.     /**
  3.      * Determine whether s3 is formed by interleaving of s1 and s2.
  4.      * @param s1, s2, s3: As description.
  5.      * @return: true or false.
  6.      */
  7.     public boolean isInterleave(String s1, String s2, String s3) {
  8.         int len1 = (s1 == null) ? 0 : s1.length();
  9.         int len2 = (s2 == null) ? 0 : s2.length();
  10.         int len3 = (s3 == null) ? 0 : s3.length();
  12.         if (len3 != len1 + len2) return false;
  14.         int i1 = 0, i2 = 0;
  15.         for (int i3 = 0; i3 < len3; i3++) {
  16.             boolean result = false;
  17.             if (i1 < len1 && s1.charAt(i1) == s3.charAt(i3) &&
  18.                 i2 < len2 && s2.charAt(i2) == s3.charAt(i3)) {
  19.                 // s1[1+i1:], s2[i2:], s3[1+i3:]
  20.                 boolean case1 = isInterleave(s1.substring(1 + i1), s2.substring(i2), s3.substring(1 + i3));
  21.                 // s1[i1:], s2[1+i2:], s3[1+i3:]
  22.                 boolean case2 = isInterleave(s1.substring(i1), s2.substring(1 + i2), s3.substring(1 + i3));
  23.                 // return instantly
  24.                 return case1 || case2;
  25.             }
  27.             if (i1 < len1 && s1.charAt(i1) == s3.charAt(i3)) {
  28.                 i1++;
  29.                 result = true;
  30.                 continue;
  31.             }
  33.             if (i2 < len2 && s2.charAt(i2) == s3.charAt(i3)) {
  34.                 i2++;
  35.                 result = true;
  36.                 continue;
  37.             }
  39.             // return instantly if both s1 and s2 can not pair with s3
  40.             if (!result) return false;
  41.         }
  43.         return true;
  44.     }
  45. }

题解3 - 动态规划

看过题解1 和 题解2 的思路后动规的状态和状态方程应该就不难推出了。按照经典的序列规划，不妨假设状态 f[i1][i2][i3] 为 s1的前i1个字符和 s2的前 i2个字符是否能交叉构成 s3的前 i3个字符，那么根据 s1[i1], s2[i2], s3[i3]的匹配情况可以分为8种情况讨论。咋一看这似乎十分麻烦，但实际上我们注意到其实还有一个隐含条件：len3 == len1 + len2, 故状态转移方程得到大幅简化。

新的状态可定义为 f[i1][i2], 含义为s1的前i1个字符和 s2的前 i2个字符是否能交叉构成 s3的前 i1 + i2 个字符。根据 s1[i1] == s3[i3] 和 s2[i2] == s3[i3] 的匹配情况可建立状态转移方程为：

  1. f[i1][i2] = (s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2]) ||
  2.             (s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1])

这道题的初始化有点 trick, 考虑到空串的可能，需要单独初始化 f[*][0] 和 f[0][*].

Python

  1. class Solution:
  2.     """
  3.     @params s1, s2, s3: Three strings as description.
  4.     @return: return True if s3 is formed by the interleaving of
  5.              s1 and s2 or False if not.
  6.     @hint: you can use [[True] * m for i in range (n)] to allocate a n*m matrix.
  7.     """
  8.     def isInterleave(self, s1, s2, s3):
  9.         len1 = 0 if s1 is None else len(s1)
  10.         len2 = 0 if s2 is None else len(s2)
  11.         len3 = 0 if s3 is None else len(s3)
  13.         if len3 != len1 + len2:
  14.             return False
  16.         f = [[True] * (1 + len2) for i in xrange (1 + len1)]
  17.         # s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2]
  18.         for i in xrange(1, 1 + len1):
  19.             f[i][0] = s1[i - 1] == s3[i - 1] and f[i - 1][0]
  20.         # s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1]
  21.         for i in xrange(1, 1 + len2):
  22.             f[0][i] = s2[i - 1] == s3[i - 1] and f[0][i - 1]
  23.         # i1 >= 1, i2 >= 1
  24.         for i1 in xrange(1, 1 + len1):
  25.             for i2 in xrange(1, 1 + len2):
  26.                 case1 = s1[i1 - 1] == s3[i1 + i2 - 1] and f[i1 - 1][i2]
  27.                 case2 = s2[i2 - 1] == s3[i1 + i2 - 1] and f[i1][i2 - 1]
  28.                 f[i1][i2] = case1 or case2
  30.         return f[len1][len2]

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * Determine whether s3 is formed by interleaving of s1 and s2.
  5.      * @param s1, s2, s3: As description.
  6.      * @return: true of false.
  7.      */
  8.     bool isInterleave(string s1, string s2, string s3) {
  9.         int len1 = s1.size();
  10.         int len2 = s2.size();
  11.         int len3 = s3.size();
  13.         if (len3 != len1 + len2) return false;
  15.         vector<vector<bool> > f(1 + len1, vector<bool>(1 + len2, true));
  16.         // s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2]
  17.         for (int i = 1; i <= len1; ++i) {
  18.             f[i][0] = s1[i - 1] == s3[i - 1] && f[i - 1][0];
  19.         }
  20.         // s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1]
  21.         for (int i = 1; i <= len2; ++i) {
  22.             f[0][i] = s2[i - 1] == s3[i - 1] && f[0][i - 1];
  23.         }
  24.         // i1 >= 1, i2 >= 1
  25.         for (int i1 = 1; i1 <= len1; ++i1) {
  26.             for (int i2 = 1; i2 <= len2; ++i2) {
  27.                 bool case1 = s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2];
  28.                 bool case2 = s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1];
  29.                 f[i1][i2] = case1 || case2;
  30.             }
  31.         }
  33.         return f[len1][len2];
  34.     }
  35. };

Java

  1. public class Solution {
  2.     /**
  3.      * Determine whether s3 is formed by interleaving of s1 and s2.
  4.      * @param s1, s2, s3: As description.
  5.      * @return: true or false.
  6.      */
  7.     public boolean isInterleave(String s1, String s2, String s3) {
  8.         int len1 = (s1 == null) ? 0 : s1.length();
  9.         int len2 = (s2 == null) ? 0 : s2.length();
  10.         int len3 = (s3 == null) ? 0 : s3.length();
  12.         if (len3 != len1 + len2) return false;
  14.         boolean [][] f = new boolean[1 + len1][1 + len2];
  15.         f[0][0] = true;
  16.         // s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2]
  17.         for (int i = 1; i <= len1; i++) {
  18.             f[i][0] = s1.charAt(i - 1) == s3.charAt(i - 1) && f[i - 1][0];
  19.         }
  20.         // s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1]
  21.         for (int i = 1; i <= len2; i++) {
  22.             f[0][i] = s2.charAt(i - 1) == s3.charAt(i - 1) && f[0][i - 1];
  23.         }
  24.         // i1 >= 1, i2 >= 1
  25.         for (int i1 = 1; i1 <= len1; i1++) {
  26.             for (int i2 = 1; i2 <= len2; i2++) {
  27.                 boolean case1 = s1.charAt(i1 - 1) == s3.charAt(i1 + i2 - 1) && f[i1 - 1][i2];
  28.                 boolean case2 = s2.charAt(i2 - 1) == s3.charAt(i1 + i2 - 1) && f[i1][i2 - 1];
  29.                 f[i1][i2] = case1 || case2;
  30.             }
  31.         }
  33.         return f[len1][len2];
  34.     }
  35. }

源码分析

为后面递推方便，初始化时数组长度多加1，for 循环时需要注意边界(取到等号)。

复杂度分析

双重 for 循环，时间复杂度为 O(n^2), 使用了二维矩阵，空间复杂度 O(n^2). 其中空间复杂度可以优化。

Reference