algoadvance

Leetcode 97. Interleaving String

Problem Statement

Given strings s1, s2, and s3, check whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where s and t are divided into n and m subsequences respectively, such that:

• s = s1 + s2 + ... + s_n
• t = t1 + t2 + ... + t_m
• |n - m| ≤ 1

The interleaved string would have all these subsequences in order but bother s and t are not reordered.

Example:

• Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

• Output: true

• Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
• Output: false

Clarifying Questions

1. Should we consider the case sensitivity of the strings?
   • Yes, strings are case-sensitive.
2. What are the constraints on the lengths of the strings?
   • Typically, the lengths of each string will not exceed 100.

Strategy

1. Edge Case Check: If the length of s3 is not equal to the sum of the lengths of s1 and s2, return false right away.
2. Dynamic Programming (DP) Approach: Use a 2D DP table where dp[i][j] means if s3 up to i+j can be formed by interleaving s1 up to i and s2 up to j.
   • The initial value dp[0][0] = true because an empty string can be formed from two empty strings.
   • For each i, j:
     • If dp[i-1][j] is true and s1[i-1] == s3[i+j-1], then set dp[i][j] to true.
     • If dp[i][j-1] is true and s2[j-1] == s3[i+j-1], then set dp[i][j] to true.
3. Return the value of dp[len(s1)][len(s2)] which tells if the full s3 can be formed by interleaving the entire s1 and s2.

Code

#include <iostream>
#include <vector>
#include <string>

bool isInterleave(std::string s1, std::string s2, std::string s3) {
    int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
    
    // Edge case check
    if (len1 + len2 != len3) {
        return false;
    }
    
    // Initialize the DP table
    std::vector<std::vector<bool>> dp(len1 + 1, std::vector<bool>(len2 + 1, false));
    dp[0][0] = true;
    
    // Fill the DP table
    for (int i = 0; i <= len1; ++i) {
        for (int j = 0; j <= len2; ++j) {
            if (i > 0) {
                dp[i][j] = dp[i][j] || (dp[i-1][j] && s1[i-1] == s3[i+j-1]);
            }
            if (j > 0) {
                dp[i][j] = dp[i][j] || (dp[i][j-1] && s2[j-1] == s3[i+j-1]);
            }
        }
    }
    
    return dp[len1][len2];
}

int main() {
    std::string s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac";
    std::cout << (isInterleave(s1, s2, s3) ? "true" : "false") << std::endl; // should return true

    s1 = "aabcc"; s2 = "dbbca"; s3 = "aadbbbaccc";
    std::cout << (isInterleave(s1, s2, s3) ? "true" : "false") << std::endl; // should return false

    return 0;
}

Time Complexity

• The time complexity of this approach is (O(n \times m)) where (n) is the length of s1 and (m) is the length of s2.
• The space complexity is also (O(n \times m)) due to the DP table.

By following the above plan, the problem can be solved efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?