Interleaving String

Share

Given strings s1, s2, s3, determine whether s3 is formed by an 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

Solution Approach

dp[i][j] = true if s3[0..i+j-1] can be formed by interleaving s1[0..i-1] and s2[0..j-1]. Transition: dp[i][j] = (dp[i-1][j] && s1[i-1]==s3[i+j-1]) || (dp[i][j-1] && s2[j-1]==s3[i+j-1]).

  • If len(s1)+len(s2) != len(s3) return false.
  • dp[0][0] = true. Initialize first row and column.
  • Fill dp table using the recurrence.
  • Return dp[m][n].
Java
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length()) return false;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <= m; i++) dp[i][0] = dp[i-1][0] && s1.charAt(i-1) == s3.charAt(i-1);
        for (int j = 1; j <= n; j++) dp[0][j] = dp[0][j-1] && s2.charAt(j-1) == s3.charAt(j-1);
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                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: O(M*N)
  • Space Complexity: O(M*N)