97. Interleaving String

97. Interleaving String (Hard)

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

Companies:
Uber

Related Topics:
String, Dynamic Programming

Solution 1. DP Top-down (DFS + Memo)

// OJ: https://leetcode.com/problems/interleaving-string/
// Author: github.com/lzl124631x
// Time: O(2^(M+N))
// Space: O(MN)
class Solution {
    int M, N;
    vector<vector<int>> m;
    int dfs(string &a, string &b, string &c, int i, int j) {
        if (i == M && j == N) return 1;
        if (m[i][j] != 0) return m[i][j];
        int val = -1;
        if (i < M && a[i] == c[i + j]) val = dfs(a, b, c, i + 1, j);
        if (val != 1 && j < N && b[j] == c[i + j]) val = dfs(a, b, c, i, j + 1);
        return m[i][j] = val;
    }
public:
    bool isInterleave(string s1, string s2, string s3) {
        M = s1.size(), N = s2.size();
        if (M + N != s3.size()) return false;
        m.assign(M + 1, vector<int>(N + 1));
        return dfs(s1, s2, s3, 0, 0) == 1;
    }
};

Solution 2. DP Bottom-up

Let dp[i][j] be whether a[0..i] and b[0..j] can form c[0..(i+j)].

dp[i][j] =  either dp[i + 1][j] if i < M && a[i] == c[i+j]
            or     dp[i][j + 1] if j < N && b[j] == c[i+j]
            or     false

dp[M][N] = true

// OJ: https://leetcode.com/problems/interleaving-string/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
    bool isInterleave(string a, string b, string c) {
        int M = a.size(), N = b.size();
        if (M + N != c.size()) return false;
        vector<vector<int>> dp(M + 1, vector<int>(N + 1));
        dp[M][N] = true;
        for (int i = M; i >= 0; --i) {
            for (int j = N; j >= 0; --j) {
                if (i < M && a[i] == c[i + j]) dp[i][j] |= dp[i + 1][j];
                if (j < N && b[j] == c[i + j]) dp[i][j] |= dp[i][j + 1];
            }
        }
        return dp[0][0];
    }
};

Solution 3. DP with Space Optimization

Since dp[i][j] is only dependent on dp[i+1][j] and dp[i][j+1], we can reduce the dp array from 2D to 1D.

// OJ: https://leetcode.com/problems/interleaving-string/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(N)
class Solution {
public:
    bool isInterleave(string a, string b, string c) {
        int M = a.size(), N = b.size();
        if (M + N != c.size()) return false;
        vector<int> dp(N + 1);
        for (int i = M; i >= 0; --i) {
            for (int j = N; j >= 0; --j) {
                if (i == M && j == N) dp[j] = true;
                else dp[j] = (i < M && a[i] == c[i + j] && dp[j])
                    || (j < N && b[j] == c[i + j] && dp[j + 1]);
            }
        }
        return dp[0];
    }
};