Description

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

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

 

Solution

用两个整型变量p1 p2维护s1 s2中已匹配字符的个数，每次尝试将s3中待匹配的字符与s1s2当前可匹配的字符相匹配，若匹配则更新p1 p2的值并加入队列的尾部，若s1+s2等于s3的长度则表明匹配成功，若队列耗尽也没匹配成功则返回失败。

这样问题就转化成了BFS，过程中会出现重复出现（一对p1 p2的值表征一个状态）相同的状态，就不必再往下搜索，否则会引起搜索超时。因此需要维护一个记录已访问状态数据结构，简单起见这里使用一个二维数组记录状态访问情况。

 

Code

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
44
45
46
47
48
49
struct state
{
    unsigned p, p1, p2;
};
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3)
    {
        if(s1.length() + s2.length() != s3.length()) return false;
        queue<state> Q;
        bool vis[1000][1000];
        memset(vis, false, sizeof(vis));
        state s = {0, 0, 0};
        Q.push(s);
        while(!Q.empty())
        {
            state s = Q.front();
            Q.pop();
            if(s.p == s3.length()) return true;
            state ns;
            if(s3[s.p] == s1[s.p1])
            {
                ns.p = s.p + 1;
                ns.p1 = s.p1 + 1;
                ns.p2 = s.p2;
                if(vis[ns.p1][ns.p2] == false)
                {
                    vis[ns.p1][ns.p2] = true;
                    Q.push(ns);
                }
            }
            if(s3[s.p] == s2[s.p2])
            {
                ns.p = s.p + 1;
                ns.p1 = s.p1;
                ns.p2 = s.p2 + 1;
                if(vis[ns.p1][ns.p2] == false)
                {
                    vis[ns.p1][ns.p2] = true;
                    Q.push(ns);
                }
            }
        }
        return false;
    }
};