Interleaving String

Description

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example
For s1 = "aabcc", s2 = "dbbca"
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Challenge:
O(n2) time or better

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true of false.
     */
    bool isInterleave(string s1, string s2, string s3) {
        // write your code here
        if (s1.size() + s2.size() != s3.size()) {
            return false;
        }
        int n1 = s1.size();
        int n2 = s2.size();
        int n3 = s3.size();
        vector<vector<bool>> dp(n1+1, vector<bool>(n2+1, false));
        dp[0][0] = true;
        // if without s2, 
        // and s3[i-1] == s1[i-1] and prefix true
        // dp[i][0]=> true
        for (int i = 1; i <= n1; i++) {
            if (s3[i - 1] == s1[i - 1] && dp[i - 1][0]) {
                 dp[i][0] = true;   
            }
        }
        // if without s1
        // and s3[i-1] == s2[i-1], and prefix true
        // dp[0][i] =true
        for (int j = 1; j <= n2; j++) {
            if (s3[j - 1] == s2[j - 1] && dp[0][j - 1]) {
                dp[0][j] = true;   
            }
        }
        // if s3[cur] == true, we need:
        // dp[i-1][j] last is true and matching last s1, s1 matching cur s3 
        // dp[j-1][i] last is true and matching last s2, s2 matching cur s3
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (
                    (s3[i + j - 1] == s1[i - 1] && dp[i - 1][j])
                    || (s3[i + j - 1] == s2[j - 1] && dp[i][j - 1])
                ) {
                    dp[i][j] = true;   
                }
            }
        }
        return dp[n1][n2];
    }
};

Similar problems

x

Tags

x