{x}
blog image

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 s and t are divided into n and m substrings respectively, such that:

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

 

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".
Since s3 can be obtained by interleaving s1 and s2, we return true.

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: Notice how it is impossible to interleave s2 with any other string to obtain s3.

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true

 

Constraints:

  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1, s2, and s3 consist of lowercase English letters.

 

Follow up: Could you solve it using only O(s2.length) additional memory space?

Solution Explanation for Interleaving String

This problem asks whether a string s3 can be formed by interleaving strings s1 and s2. We can solve this using dynamic programming or memoization.

Approach:

Both solutions leverage the idea of building a table (or using memoization to simulate a table) to track whether a prefix of s3 can be formed by interleaving prefixes of s1 and s2.

Solution 1: Memoization Search

This approach uses recursion with memoization to avoid redundant calculations.

  • dfs(i, j): This recursive function checks if the suffix of s3 starting from index i + j can be formed by interleaving the suffixes of s1 (starting from i) and s2 (starting from j).
  • Base Case: If i and j reach the end of s1 and s2 respectively, it means we've successfully interleaved all characters, so we return true.
  • Recursive Step: We check if the current character of s3 (s3[i + j]) matches either s1[i] or s2[j]. If a match is found, we recursively call dfs with the next index in the corresponding string. If both recursive calls return false, it implies that no valid interleaving exists, so we return false.
  • Memoization: A cache (@cache in Python, HashMap in Java etc.) stores the results of dfs(i, j) to prevent recalculations.

Solution 2: Dynamic Programming

This approach uses a 2D boolean array f to store the results. f[i][j] is true if the first i characters of s1 and the first j characters of s2 can interleave to form the first i + j characters of s3, and false otherwise.

  • Initialization: f[0][0] = true (an empty string is an interleaving of two empty strings).
  • Iteration: The table is filled iteratively. f[i][j] is true if either f[i-1][j] (using the current character from s1) or f[i][j-1] (using the current character from s2) is true and the corresponding character matches s3[i+j-1].
  • Result: f[m][n] (where m and n are lengths of s1 and s2) contains the final answer.

Space Optimization (Solution 2):

The dynamic programming solution can be further optimized to use only O(n) space by using a rolling array (or a single 1D array). This is because we only need to access the previous row (or column) to compute the current row (or column). The provided codes show this optimization.

Time Complexity:

Both solutions have a time complexity of O(m*n), where m and n are the lengths of s1 and s2 respectively. This is because we iterate through all possible combinations of prefixes of s1 and s2.

Space Complexity:

  • Solution 1 (Memoization): O(m*n) in the worst case (if the cache is fully populated).
  • Solution 2 (Dynamic Programming): O(m*n) initially, but can be optimized to O(n) using the rolling array technique.

The provided code examples in various languages demonstrate both approaches, with the space-optimized dynamic programming solution being generally preferred for its efficiency. Remember to handle edge cases like empty input strings.