LeetCode-Interleaving Strings 解题报告

Question

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.

首先想到的是一个回溯的方法。可以看作一个二叉树的遍历过程，匹配到s1的字符就是走左子节点，匹配到s2的字符就是走右子节点。若s1和s2中的两个字符都和s3相同，就有两种选择，直接都取s1的，并且把这时s1和s2的索引存下来，遇到后面匹配失败的时候找前一个存下来的索引，从s2走，也就是回溯了。无奈，超时了。时间复杂度应该是，m和n分别是s1和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
 bool isInterleave(string s1, string s2, string s3) {
     stack<int> st;
     int idx1 = 0;
     int idx2 = 0;
     int n1 = s1.size();
     int n2 = s2.size();
     int n3 = s3.size();
     if (n1 + n2 != n3) return false;
     for (int i = 0; i < n3; i++) {
         if (idx1 < n1 && s3[i] == s1[idx1]) {
             if (s1[idx1] == s2[idx2]) {
                 st.push(idx1);
                 st.push(idx2);
                 st.push(i);
             }
             idx1++;
         } else if (idx2 < n2 && s3[i] == s2[idx2]) {
             idx2++;
         } else if (!st.empty()) {
             i = st.top();
             st.pop();
             idx2 = st.top()+1;
             st.pop();
             idx1 = st.top();
             st.pop();
         } else
             return false;
     }
     return true;
 }
// 回溯，TLE

然后又无脑地换成了广搜，结果更加TLE，时间复杂度跟回溯一样，空间复杂度倒更大了。

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
bool isInterleave(string s1, string s2, string s3) {
    int idx1, idx2, idx3;
    int n1 = s1.size();
    int n2 = s2.size();
    int n3 = s3.size();
    if (n1 + n2 != n3) return false;
    if (n1 == 0 && n2 == 0 && n3 == 0) return true;
    queue< vector<int> > route;
    vector<int> temp = {0,0,0};
    route.push(temp);
    while(!route.empty()) {
        idx1 = route.front()[0];
        idx2 = route.front()[1];
        idx3 = route.front()[2];
        if (idx1 < n1 && s3[idx3] == s1[idx1]) {
//            cout << idx1 << " " << idx2 << " " << idx3 << endl;
            if (idx3 == n3-1) return true;
            temp = {idx1+1, idx2, idx3+1};
            route.push(temp);
        }
        if (idx2 < n2 && s3[idx3] == s2[idx2]) {
//            cout << idx1 << " " << idx2 << " " << idx3 << endl;
            if (idx3 == n3-1) return true;
            temp = {idx1, idx2+1, idx3+1};
            route.push(temp);
        }
        route.pop();
    }
    return false;
}
// BFS，更加TLE

最后瞄了一眼答案的时间复杂度是O(m*n)，硬着头皮还是写出了动态规划的解法。用bool dp[i][j]表示可以从头匹配到s1的第i个位置和s2的第j个位置。注意取了一个dp[0][0] = true作为dummy head。当dp[i][j]为真且s1[i] == s3[i+j]，也就是匹配到了s1的第i个位置和s2的第j个位置（从1开始），下一个要匹配的字符是s3[i+j]，即s3的第i+j+1个字符，而s1的第i+1个字符和它相等，所以dp[i+1][j]为真。匹配s2的时候同理。最后一个位置n1和n2的时候要判断一下以免下标越界。时间和空间复杂度都是O(m*n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool isInterleave(string s1, string s2, string s3) {
    int n1 = s1.size();
    int n2 = s2.size();
    int n3 = s3.size();
    if (n1 + n2 != n3) return false;
    if (n1 == 0 && n2 == 0 && n3 == 0) return true;
    vector< vector<bool> > dp(n1+1, vector<bool>(n2+1));
    dp[0][0] = true; 
    for (int i = 0; i < n1+1; i++) {
        for (int j = 0; j < n2+1; j++) {
            if (i == n1 && j == n2)
                return dp[n1][n2];
            else {
                if (i != n1 && dp[i][j] && s1[i] == s3[i+j])
                    dp[i+1][j] = true;
                if (j != n2 && dp[i][j] && s2[j] == s3[i+j])
                    dp[i][j+1] = true;
            }
        }
    }
    return dp[n1][n2];
}

假如把动态规划的这个方法也看成一个二叉树的遍历过程，在这个特定问题里，下一个匹配的字符的判断并不依赖于之前访问的路径而只依赖于之前访问的结果，即向左一步向右两步和向右两步向左一步是等价的。相比回溯和BFS，它的效率提升在于两个地方：

  1. 节省了通过不同路径重复获取同一结果的运算；
  2. 在j的for循环中，每一个j的迭代可以访问多条路径（如在多种dp[i][j] == true的二叉树访问路径的case下求dp[i][j+1]）。回溯和BFS访问的顺序并不能满足这样多条路径的递推求解条件。

Editorial Solution中的Approach 2通过存储访问结果解决了1。动态规划的方法Approach 4把二维数组换成了一维数组，空间复杂度变成了O(n)。