题目描述（困难难度）

97. Interleaving String - 图1

在两个字符串 s1 和 s2 中依次取字母，问是否可以组成 S3。什么意思呢？比如 s1 = abc , s2 = de，s3 = abdce。

s1 取 1 个 字母得到 a，s1 再取个字母得到 ab，s2 取个字母得到 abd， s1 取 1 个 字母得到 abdc， s2 取 1 个 字母得到 abdce，然后就得到了 s3，所以返回 true。

解法一 回溯法

如果我们简化下问题，如果 s1 和 s2 中不含有重复的字母，比如 s1 = abc，s2 = de，s3 = abdce。

这样是不是就简单多了。我们只需要三个指针，依次遍历字符串。

  1. i 和 k 的指的字母相等，所以 i 后移，k 后移
  2. a b c
  3. ^
  4. i
  6. d e
  7. ^
  8. j
  10. a b d c e
  11. ^
  12. k
  14. i 和 k 的指的字母相等，所以 i 后移，k 后移
  15. a b c
  16.   ^
  17.   i
  19. d e
  20. ^
  21. j
  23. a b d c e
  24.   ^
  25.   k
  27. j 和 k 的指的字母相等，所以 j 后移，k 后移
  28. a b c
  29.     ^
  30.     i
  32. d e
  33. ^
  34. j
  36. a b d c e
  37.     ^
  38.     k
  40. 就这样比较下去，如果 i,j,k 都成功移动到了末尾即成功。

但是这道题 s1 和 s2 中会有重复的字符出现，比如下边的情况

  1. a d c
  2.   ^
  3.   i
  5. d e
  6. ^
  7. j
  9. a d c e
  10.   ^
  11.   k

此时 i 和 j 指向的字母都和 k 相等，此时该怎么办呢？

回溯法！是的，我们先尝试 i 和 k 后移，然后看能不能成功。不行的话我们再回溯回来，把 j 和 k 后移。

  1. public boolean isInterleave(String s1, String s2, String s3) {
  2.     return getAns(s1, 0, s2, 0, s3, 0);
  3. }
  5. private boolean getAns(String s1, int i, String s2, int j, String s3, int k) {
  6.     //长度不匹配直接返回 false
  7.     if (s1.length() + s2.length() != s3.length()) {
  8.         return false;
  9.     }
  10.     // i、j、k 全部达到了末尾就返回 true
  11.     if (i == s1.length() && j == s2.length() && k == s3.length()) {
  12.         return true;
  13.     }
  14.     // i 到达了末尾，直接移动 j 和 k 不停比较
  15.     if (i == s1.length()) {
  16.         while (j < s2.length()) {
  17.             if (s2.charAt(j) != s3.charAt(k)) {
  18.                 return false;
  19.             }
  20.             j++;
  21.             k++;
  22.         }
  23.         return true;
  24.     }
  25.     // j 到达了末尾，直接移动 i 和 k 不停比较
  26.     if (j == s2.length()) {
  27.         while (i < s1.length()) {
  28.             if (s1.charAt(i) != s3.charAt(k)) {
  29.                 return false;
  30.             }
  31.             i++;
  32.             k++;
  33.         }
  34.         return true;
  35.     }
  36.     //判断 i 和 k 指向的字符是否相等
  37.     if (s1.charAt(i) == s3.charAt(k)) {
  38.         //后移 i 和 k 继续判断，如果成功了直接返回 true
  39.         if (getAns(s1, i + 1, s2, j, s3, k + 1)) {
  40.             return true;
  41.         }
  42.     }
  43.     //移动 i 和 k 失败，尝试移动 j 和 k
  44.     if (s2.charAt(j) == s3.charAt(k)) {
  45.         if (getAns(s1, i, s2, j + 1, s3, k + 1)) {
  46.             return true;
  47.         }
  48.     }
  49.     //移动 i 和 j 都失败，返回 false
  50.     return false;
  51. }

让我们优化一下，由于递归的分支，所以会造成很多重复情况的判断，所以我们用 memoization 技术，把求出的结果用 hashmap 保存起来，第二次过来的时候直接返回结果以免再次进入递归。

用 1 表示 true，0 表示 false，-1 代表还未赋值。

hashmap key 的话用字符串 i + “@” + j ，之所以中间加 “@”，是为了防止 i = 1 和 j = 22。以及 i = 12，j = 2。这样的两种情况产生的就都是 122。加上 “@” 可以区分开来。

  1. public boolean isInterleave(String s1, String s2, String s3) {
  2.     HashMap<String, Integer> memoization = new HashMap<>();
  3.     return getAns(s1, 0, s2, 0, s3, 0, memoization);
  4. }
  6. private boolean getAns(String s1, int i, String s2, int j, String s3, int k, HashMap<String, Integer> memoization) {
  7.     if (s1.length() + s2.length() != s3.length()) {
  8.         return false;
  9.     }
  10.     String key = i + "@" + j;
  11.     if (memoization.containsKey(key)) {
  12.         return memoization.getOrDefault(key, -1) == 1;
  13.     }
  14.     if (i == s1.length() && j == s2.length() && k == s3.length()) {
  15.         memoization.put(key, 1);
  16.         return true;
  17.     }
  18.     if (i == s1.length()) {
  19.         while (j < s2.length()) {
  20.             if (s2.charAt(j) != s3.charAt(k)) {
  21.                 memoization.put(key, 0);
  22.                 return false;
  23.             }
  24.             j++;
  25.             k++;
  26.         }
  27.         memoization.put(key, 1);
  28.         return true;
  29.     }
  31.     if (j == s2.length()) {
  32.         while (i < s1.length()) {
  33.             if (s1.charAt(i) != s3.charAt(k)) {
  34.                 memoization.put(key, 0);
  35.                 return false;
  36.             }
  37.             i++;
  38.             k++;
  39.         }
  40.         memoization.put(key, 1);
  41.         return true;
  42.     }
  43.     if (s1.charAt(i) == s3.charAt(k)) {
  44.         if (getAns(s1, i + 1, s2, j, s3, k + 1, memoization)) {
  45.             memoization.put(key, 1);
  46.             return true;
  47.         }
  48.     }
  49.     if (s2.charAt(j) == s3.charAt(k)) {
  50.         if (getAns(s1, i, s2, j + 1, s3, k + 1, memoization)) {
  51.             memoization.put(key, 1);
  52.             return true;
  53.         }
  54.     }
  55.     memoization.put(key, 0);
  56.     return false;
  57. }

解法二 动态规划

参考这里。

其实和递归本质上是一样的，解法一中压栈到末尾最后一个字符的时候，再次压栈，就会进入 if (i == s1.length() && j == s2.length() && k == s3.length()) 这里，然后就开始一系列的出栈过程。

而动态规划就是利用一个 dp 数组去省去压栈，所谓空间换时间。这里的话，我们也不模仿递归从尾部开始了，我们直接从开头开始，思想是一样的。

我们定义一个 boolean 二维数组 dp [ i ] [ j ] 来表示 s1[ 0, i ) 和 s2 [ 0, j ） 组合后能否构成 s3 [ 0, i + j )，注意不包括右边界，主要是为了考虑开始的时候如果只取 s1，那么 s2 就是空串，这样的话 dp [ i ] [ 0 ] 就能表示 s2 取空串。

状态转换方程也很好写了，如果要求 dp [ i ] [ j ] 。

如果 dp [ i - 1 ] [ j ] == true，并且 s1 [ i - 1 ] == s3 [ i + j - 1]， dp [ i ] [ j ] = true 。

如果 dp [ i ] [ j - 1 ] == true，并且 s2 [ j - 1 ] == s3 [ i + j - 1]， dp [ i ] [ j ] = true 。

否则的话，就更新为 dp [ i ] [ j ] = false。

如果 i 为 0，或者 j 为 0，那直接判断 s2 和 s3 对应的字母或者 s1 和 s3 对应的字母即可。

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

然后就是老规矩了，空间复杂度的优化，例如5题，10题，53题，72题等等都是同样的思路。都是注意到一个特点，当更新到 dp [ i ] [ j ] 的时候，我们只用到 dp [ i - 1 ] [ j ] ，即上一层的数据，再之前的数据就没有用了。所以我们不需要二维数组，只需要一个一维数组就够了。

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

解法三 广度优先遍历 BFS

参考这里。我们把问题抽象一下。

97. Interleaving String - 图2

从左上角到达右下角，遍历过程加上边对应的字符，最后就可以产生 S3 了。回想一下，解法一递归的遍历过程，其实就是图的深度遍历，从 0 位置出发，一致尝试向右，不行的话就回溯，再尝试向下，然后再开始尝试向右，直到右下角。像一只贪婪的蛇，认准目标直奔而去。

而解法一开始没有优化前讲到说会有很多重复的解，结合上边的图也刚好理解了。因为开始尝试了条路后，回退回退回退，然后再向前的时候就可能回到原来的路上了。

这里的话，既然都已经抽象出一个图了，所以除了 DFS，当然还有 BFS。尝试遍历整个图，如果到达了右下角就返回 true。

当然任意两个节点并不是都可以到达的，只有当前要遍历的 S1 或者 S2 对应的字母和 S3 相应的字母相等我们才可以遍历。

用一个队列保存可以遍历的节点，然后不停的从队列里取元素，然后把可以到达的新的节点加到队列中。

  1. class Point {
  2.     int x;
  3.     int y;
  5.     Point(int x, int y) {
  6.         this.x = x;
  7.         this.y = y;
  8.     }
  9. }
  10. class Solution {
  11.     public boolean isInterleave(String s1, String s2, String s3) {
  12.     if (s1.length() + s2.length() != s3.length()) {
  13.         return false;
  14.     }
  15.     Queue<Point> queue = new LinkedList<Point>();
  16.     queue.add(new Point(0, 0));
  17.     //判断是否已经遍历过
  18.     boolean[][] visited = new boolean[s1.length() + 1][s2.length() + 1];
  19.     while (!queue.isEmpty()) {
  20.         Point cur = queue.poll();
  21.         //到达右下角就返回 true
  22.         if (cur.x == s1.length() && cur.y == s2.length()) {
  23.             return true;
  24.         }
  25.         // 尝试是否能向右走
  26.         int right = cur.x + 1;
  27.         if (right <= s1.length() && s1.charAt(right - 1) == s3.charAt(right + cur.y - 1)) {
  28.             if (!visited[right][cur.y]) {
  29.                 visited[right][cur.y] = true;
  30.                 queue.offer(new Point(right, cur.y));
  31.             }
  32.         }
  34.         // 尝试是否能向下走
  35.         int down = cur.y + 1;
  36.         if (down <= s2.length() && s2.charAt(down - 1) == s3.charAt(down + cur.x - 1)) {
  37.             if (!visited[cur.x][down]) {
  38.                 visited[cur.x][down] = true;
  39.                 queue.offer(new Point(cur.x, down));
  40.             }
  41.         }
  43.     }
  44.     return false;
  45. }
  46. }

总

很经典的一道题了，第一次用到了 BFS，之前都是 DFS。最后的图，其实把所有的解法的本质都揭露了出来。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情