本文已参加「新人创造礼」活动,一同敞开创造之路。

leetcode第97题

题目描绘（中等难度）

在两个字符串 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。

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

i 和 k 的指的字母持平，所以 i 后移，k 后移
a b c
^
i
​
d e
^
j
​
a b d c e
^
k
​
i 和 k 的指的字母持平，所以 i 后移，k 后移
a b c
 ^
 i
​
d e
^
j
​
a b d c e
 ^
 k
​
j 和 k 的指的字母持平，所以 j 后移，k 后移
a b c
  ^
  i
​
d e
^
j
​
a b d c e
  ^
  k
​
就这样比较下去，假如 i,j,k 都成功移动到了结尾即成功。
​

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

a d c
 ^
 i
​
d e
^
j
​
a d c e
 ^
 k

此刻 i 和 j 指向的字母都和 k 持平，此刻该怎么办呢？

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

public boolean isInterleave(String s1, String s2, String s3) {
  return getAns(s1, 0, s2, 0, s3, 0);
}
​
private boolean getAns(String s1, int i, String s2, int j, String s3, int k) {
  //长度不匹配直接回来 false
  if (s1.length() + s2.length() != s3.length()) {
    return false;
   }
  // i、j、k 悉数达到了结尾就回来 true
  if (i == s1.length() && j == s2.length() && k == s3.length()) {
    return true;
   }
  // i 抵达了结尾，直接移动 j 和 k 不断比较
  if (i == s1.length()) {
    while (j < s2.length()) {
      if (s2.charAt(j) != s3.charAt(k)) {
        return false;
       }
      j++;
      k++;
     }
    return true;
   }
  // j 抵达了结尾，直接移动 i 和 k 不断比较
  if (j == s2.length()) {
    while (i < s1.length()) {
      if (s1.charAt(i) != s3.charAt(k)) {
        return false;
       }
      i++;
      k++;
     }
    return true;
   }
  //判别 i 和 k 指向的字符是否持平
  if (s1.charAt(i) == s3.charAt(k)) {
    //后移 i 和 k 继续判别，假如成功了直接回来 true
    if (getAns(s1, i + 1, s2, j, s3, k + 1)) {
      return true;
     }
   }
  //移动 i 和 k 失利，测验移动 j 和 k
  if (s2.charAt(j) == s3.charAt(k)) {
    if (getAns(s1, i, s2, j + 1, s3, k + 1)) {
      return true;
     }
   }
  //移动 i 和 j 都失利，回来 false
  return false;
}

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

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

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

public boolean isInterleave(String s1, String s2, String s3) {
  HashMap<String, Integer> memoization = new HashMap<>();
  return getAns(s1, 0, s2, 0, s3, 0, memoization);
}
​
private boolean getAns(String s1, int i, String s2, int j, String s3, int k, HashMap<String, Integer> memoization) {
  if (s1.length() + s2.length() != s3.length()) {
    return false;
   }
  String key = i + "@" + j;
  if (memoization.containsKey(key)) {
    return memoization.getOrDefault(key, -1) == 1;
   }
  if (i == s1.length() && j == s2.length() && k == s3.length()) {
    memoization.put(key, 1);
    return true;
   }
  if (i == s1.length()) {
    while (j < s2.length()) {
      if (s2.charAt(j) != s3.charAt(k)) {
        memoization.put(key, 0);
        return false;
       }
      j++;
      k++;
     }
    memoization.put(key, 1);
    return true;
   }
​
  if (j == s2.length()) {
    while (i < s1.length()) {
      if (s1.charAt(i) != s3.charAt(k)) {
        memoization.put(key, 0);
        return false;
       }
      i++;
      k++;
     }
    memoization.put(key, 1);
    return true;
   }
  if (s1.charAt(i) == s3.charAt(k)) {
    if (getAns(s1, i + 1, s2, j, s3, k + 1, memoization)) {
      memoization.put(key, 1);
      return true;
     }
   }
  if (s2.charAt(j) == s3.charAt(k)) {
    if (getAns(s1, i, s2, j + 1, s3, k + 1, memoization)) {
      memoization.put(key, 1);
      return true;
     }
   }
  memoization.put(key, 0);
  return false;
}

解法二 动态规划

参考这儿。

其实和递归本质上是相同的，解法一中压栈到结尾最终一个字符的时分，再次压栈，就会进入 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 对应的字母即可。

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

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

public boolean isInterleave(String s1, String s2, String s3) {
  if (s1.length() + s2.length() != s3.length()) {
    return false;
   }
  boolean[] dp = 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) {
        dp[j] = true;
       } else if (i == 0) {
        dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
       } else if (j == 0) {
        dp[j] = dp[j] && s1.charAt(i - 1) == s3.charAt(i - 1);
       } else {
        dp[j] = dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)
          || dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
       }
     }
   }
  return dp[s2.length()];
}

解法三 广度优先遍历 BFS

参考这儿。咱们把问题笼统一下。

从左上角抵达右下角，遍历进程加上边对应的字符，最终就能够发生 S3 了。回想一下，解法一递归的遍历进程，其实就是图的深度遍历，从 0 位置动身，共同测验向右，不行的话就回溯，再测验向下，然后再开端测验向右，直到右下角。像一只贪婪的蛇，认准方针直奔而去。

而解法一开端没有优化前讲到说会有很多重复的解，结合上边的图也刚好理解了。由于开端测验了条路后，回退回退回退，然后再向前的时分就可能回到原来的路上了。

这儿的话，已然都现已笼统出一个图了，所以除了 DFS，当然还有 BFS。测验遍历整个图，假如抵达了右下角就回来 true。

当然恣意两个节点并不是都能够抵达的，只有当前要遍历的 S1 或许 S2 对应的字母和 S3 相应的字母持平咱们才能够遍历。

用一个行列保存能够遍历的节点，然后不断的从行列里取元素，然后把能够抵达的新的节点加到行列中。

class Point {
  int x;
  int y;
​
  Point(int x, int y) {
    this.x = x;
    this.y = y;
   }
}
class Solution {
  public boolean isInterleave(String s1, String s2, String s3) {
  if (s1.length() + s2.length() != s3.length()) {
    return false;
   }
  Queue<Point> queue = new LinkedList<Point>();
  queue.add(new Point(0, 0));
  //判别是否现已遍历过
  boolean[][] visited = new boolean[s1.length() + 1][s2.length() + 1];
  while (!queue.isEmpty()) {
    Point cur = queue.poll();
    //抵达右下角就回来 true
    if (cur.x == s1.length() && cur.y == s2.length()) {
      return true;
     }
    // 测验是否能向右走
    int right = cur.x + 1;
    if (right <= s1.length() && s1.charAt(right - 1) == s3.charAt(right + cur.y - 1)) {
      if (!visited[right][cur.y]) {
        visited[right][cur.y] = true;
        queue.offer(new Point(right, cur.y));
       }
     }
​
    // 测验是否能向下走
    int down = cur.y + 1;
    if (down <= s2.length() && s2.charAt(down - 1) == s3.charAt(down + cur.x - 1)) {
      if (!visited[cur.x][down]) {
        visited[cur.x][down] = true;
        queue.offer(new Point(cur.x, down));
       }
     }
​
   }
  return false;
}
​

总结

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