[LeetCode] 97. Interleaving String

Posted on | In

Problem

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

Example 1:

1
2
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

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

Explanation

  1. We can use dynamic programming to solve this problem.

  2. Dynamic state is a two dimensional boolean array dp[i][j], which means the result of choosing s1’s character from beginning to the ith character inclusive and s2’s character from beginning to the jth character inclusive to check if they are interleaving with s3 of choosing from the beginning to the i+jth character.

  3. Dynamic init is dp[0][0] = true because if s1 and s2 are empty, then they are interleaving of s3 with choosing zero length.

  4. Dynamic function: If s1’s length is the row and s2’s length is the column, and we want to find the result of dp[i][j], then if s1’s last character which is the ith character is the same as the s3’s last character which is the i+jth character, then the result of dp[i][j] is the same as dp[i-1][j] (top). Similarlly, if s2’s last character is the same as s3’s last character, then the result of dp[i][j] is the same as dp[i][j-1] (left).

  5. Dynamic result is choosing all character of s1 and choosing all character of s2, so it’s in the bottom right, which is dp[s1.length()][s2.length()].

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1 == null || s2 == null || s3 == null) return false;
        if (s1.length() + s2.length() != s3.length()) return false;

        boolean[][] dp = new boolean[s1.length()+1][s2.length()+1];
        dp[0][0] = true;

        for (int i = 0; i <= s3.length(); i++) {
            for (int s1Len = 0; s1Len <= i && s1Len <= s1.length(); s1Len++) {
                int s2Len = i - s1Len;
                if (s2Len > s2.length()) continue;
                if (s1Len > 0 && dp[s1Len-1][s2Len] && s3.charAt(i-1) == s1.charAt(s1Len-1)) {
                    dp[s1Len][s2Len] = true;
                } else if (s2Len > 0 && dp[s1Len][s2Len-1] && s3.charAt(i-1) == s2.charAt(s2Len-1)) {
                    dp[s1Len][s2Len] = true;
                }
            }
        }

        return dp[s1.length()][s2.length()];
    }
}