algoadvance

Leetcode 97. Interleaving String

Problem Statement

97. Interleaving String

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

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| >= 0
• The interleaving string is s1 + t1 + s2 + t2 + ... (for any valid arrangement).

Clarifying Questions

1. Are the input strings always non-empty? Yes, input strings are non-empty in the general case.

2. Are the characters in the strings always lowercase English letters? Yes, the strings contain only lowercase English letters.

3. Can s1 or s2 be entirely used up before the interleaving completes? Yes, once one string is used up, the rest of the other string should match the remaining part of s3.

4. What’s the maximum length for the strings? Each of the strings can have a length up to 100.

Strategy

To solve the problem, we can use Dynamic Programming (DP).

1. DP Table Definition:
   • We’ll define a 2D DP table where dp[i][j] represents if s3 up to the (i + j)th position can be formed by interleaving s1 up to the ith position and s2 up to the jth position.
2. Initialization:
   • dp[0][0] should be true because an empty s1 and s2 can form an empty s3.
3. DP Transition:
   • For position dp[i][j], check:
     • If the previous position in s1 can create a valid interleave (dp[i - 1][j]) and the i-th character of s1 matches the current character of s3.
     • Or if the previous position in s2 can create a valid interleave (dp[i][j - 1]) and the j-th character of s2 matches the current character of s3.
4. Result:
   • The value at dp[length of s1][length of s2] will be our answer.

Code

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        
        if (m + n != s3.length()) {
            return false;
        }
        
        boolean[][] dp = new boolean[m + 1][n + 1];
        
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                } else if (i == 0) {
                    dp[i][j] = dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
                } else {
                    dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) ||
                               (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
                }
            }
        }
        
        return dp[m][n];
    }
}

Time Complexity

• Time Complexity: O(m * n), where m and n are the lengths of s1 and s2. We need to fill an (m+1) x (n+1) table.
• Space Complexity: O(m * n) as we need to store the result of subproblems in a 2D array.

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?