## 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

`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> 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]; } }; ``````