Question
Formatted question description: https://leetcode.ca/all/97.html
97 Interleaving String
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
@tag-dp
Algorithm
Manually write out the two-dimensional array dp as follows:
Ø d b b c a
Ø T F F F F F
a T F F F F F
a T T T T T F
b F T T F T F
c F F T T T T
c F F F T F T
The major premise of this question is that the sum of the lengths of the strings s1
and s2
must be equal to the length of s3
. If they are not equal, false is definitely returned.
Then when s1 and s2 are empty strings, s3 must be an empty string, and true is returned. So directly assign true to dp[0][0]
,
And then if one of s1 and s2 is an empty string, then the other must have the same length as s3, and then compare bitwise. If the same and the previous position is true, set True for dp, and assign False in other cases, so that the edge of the two-dimensional array dp is initialized.
Next, we only need to find the state transition equation to update the entire array. We found that at any non-edge position dp[i][j]
, its left or upper side may be True or False, and both sides can be updated. As long as there is a path through, then this point can be True. Then we have to look at it separately, if the left one is True, then we remove the character string s2[j-1]
in the current corresponding s2 compared with the character in the corresponding position in s3 (when calculating the corresponding position, consider the matched The character in s1) is s3[j-1 + i]
. If they are equal, then assign True, otherwise assign False. The situation where the above is True is similar, so the state transition equation can be calculated as:
dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i-1 + j]) || (dp[i][j-1] && s2 [j-1] == s3[j-1 + i]);
- Where
dp[i][j]
indicates whether the firsti
characters of s2 and the firstj
characters of s1 match the firsti+j
characters of s3
Code
Java
-
public class Interleaving_String { public class Solution { public boolean isInterleave(String s1, String s2, String s3) { if (s1.length() == 0 || s1 == null) { return s2.equals(s3); } if (s2.length() == 0 || s2 == null) { return s1.equals(s3); } // @note: missed this simple check if (s1.length() + s2.length() != s3.length()) { return false; } // 1-to-i of s1, and 1-to-j of s2, can for 1-to-(i+j) of s3 boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1]; // +1 for empty string dp[0][0] = true; // pre-process for empty string case for (int i = 1; i < s1.length() + 1; i++) { dp[i][0] = (s1.charAt(i - 1) == s3.charAt(i - 1)) && dp[i - 1][0]; } for (int i = 1; i < s2.length() + 1; i++) { dp[0][i] = (s2.charAt(i - 1) == s3.charAt(i - 1)) && dp[0][i - 1]; } for (int i = 1; i < s1.length() + 1; i++) { for (int j = 1; j < s2.length() + 1; j++) { boolean withS1 = s1.charAt(i - 1) == s3.charAt(i - 1 + j) && dp[i - 1][j]; boolean withS2 = s2.charAt(j - 1) == s3.charAt(i - 1 + j) && dp[i][j - 1]; dp[i][j] = withS1 || withS2; } } return dp[s1.length()][s2.length()]; } } public class Solution_over_time { public boolean isInterleave(String s1, String s2, String s3) { if (s1.length() == 0 || s1 == null) { return s2.equals(s3); } if (s2.length() == 0 || s2 == null) { return s1.equals(s3); } boolean withS1 = false; boolean withS2 = false; if (s1.charAt(0) == s3.charAt(0)) { withS1 = isInterleave(s1.substring(1), s2, s3.substring(1)); } if (s2.charAt(0) == s3.charAt(0)) { withS2 = isInterleave(s1, s2.substring(1), s3.substring(1)); } return withS1 || withS2; } } }
-
// OJ: https://leetcode.com/problems/interleaving-string/ // Time: O(2^(M+N)) // Space: O(MN) class Solution { int M, N; vector<vector<int>> m; int dfs(string &a, string &b, string &c, int i, int j) { if (i == M && j == N) return 1; if (m[i][j] != 0) return m[i][j]; int val = -1; if (i < M && a[i] == c[i + j]) val = dfs(a, b, c, i + 1, j); if (val != 1 && j < N && b[j] == c[i + j]) val = dfs(a, b, c, i, j + 1); return m[i][j] = val; } public: bool isInterleave(string s1, string s2, string s3) { M = s1.size(), N = s2.size(); if (M + N != s3.size()) return false; m.assign(M + 1, vector<int>(N + 1)); return dfs(s1, s2, s3, 0, 0) == 1; } };
-
class Solution(object): def isInterleave(self, s1, s2, s3): """ :type s1: str :type s2: str :type s3: str :rtype: bool """ d = {} s3 = list(s3) if len(s1) + len(s2) != len(s3): return False def dfs(s1, i, s2, j, d, path, s3): if (i, j) in d: return d[(i, j)] if path == s3: return True if i < len(s1): if s3[i + j] == s1[i]: path.append(s1[i]) if dfs(s1, i + 1, s2, j, d, path, s3): return True path.pop() d[(i + 1, j)] = False if j < len(s2): if s3[i + j] == s2[j]: path.append(s2[j]) if dfs(s1, i, s2, j + 1, d, path, s3): return True path.pop() d[(i, j + 1)] = False return False return dfs(s1, 0, s2, 0, d, [], s3)