Description

Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"

Output: false

Solution

题目：

判断s3是否由s1、s2相互交错而成。

解：

判断由s1、s2组成的地图，是否存在路径s3；

Example1如下图，有多个解：

Example1:

s3: aadbbcbcac

    a a b c c   (s1)
    a_a
  d   d
  b   b
  b   b
  c   c_b_c
  a       a_c

(s2)

    a a b c c   (s1)
    a_a
  d   d_b
  b     b_c
  b       b
  c       c
  a       a_c

(s2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        auto width = s1.length() + 1;
        auto height = s2.length() + 1;

        if (width + height - 2 != s3.length()) {
            return false;
        }

        if (width == 1 || height == 1) {
            return (s1.compare(s3) == 0) || (s2.compare(s3) == 0);
        }

        std::vector<std::vector<bool>> dp;
        dp.resize(width);
        for (auto &v : dp) {
            v.resize(height);
        }

        // 初始化第一个位置，然后在循环中判断是否可能往右边/下边走。
        dp[0][0] = true;

        for (int i = 0; i < width; ++i) {
            for (int j = i == 0 ? 1: 0; j < height; ++j) {
                char c = s3.at(j + i - 1);

                // 尝试吃掉s1的字符，则只能由左边走过来
                // 如果是上方格子为true,表示当前字符已经使用，不能再次使用
                if (i > 0 && s1.at(i - 1) == c && dp[i-1][j]) {
                    dp[i][j] = true;
                }

                // 尝试吃掉s2的字符，则只能由上边走过来
                if (j > 0 && s2.at(j - 1) == c && dp[i][j-1]) {
                    dp[i][j] = true;
                }
            }
        }

        return dp[width-1][height-1];
    }
};