This content originally appeared on DEV Community and was authored by seanpgallivan
This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #97 (Medium): Interleaving String
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
Given strings
s1,s2, ands3, find whethers3is formed by an interleaving ofs1ands2.An interleaving of two strings
sandtis a configuration where they are divided into non-empty substrings such that:
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- The interleaving is
s1 + t1 + s2 + t2 + s3 + t3 + ...ort1 + s1 + t2 + s2 + t3 + s3 + ...Note:
a + bis the concatenation of stringsaandb.
Examples:
Example 1: Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true Visual:
Example 2: Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false
Example 3: Input: s1 = "", s2 = "", s3 = "" Output: true
Constraints:
0 <= s1.length, s2.length <= 1000 <= s3.length <= 200s1,s2, ands3consist of lowercase English letters.
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
If we consider a matrix with indices (i) for s1 on one axis and indices (j) for s2 on the other, then a successful s3 can be considered a path moving from the top left to the bottom right. At each point, we either move downward (i++) by choosing the next letter from s1 or rightward (j++) by choosing the next letter from s2.
All that remains, then, is to see which vertices are possible given s3, and which ones are not. To do that, we can use a dynamic programming (DP) approach. We should establish a matrix (dp) as described above, along with a buffer row/column to the start of dp to provide space for previous row/column validation checks for the leading edges of our iteration.
Since cells are validated from the left or from above, we should also remember to fill either the cell to the left or above the initial cell (dp[0][1] or dp[1][0]) with a true (or 1) value, representing a valid vertex at the starting position of our iteration path.
From there, we can iterate through the matrix rightward and downward, building upon previously completed entries to check the validity of the current cell. If the cell above is valid (true or 1) and the corresponding characters of s1 and s3 match, then the current cell is valid. Similarly, if the cell to the left is valid and the corresponding characters of s2 and s3 match, then the current cell is valid.
Once we've finished iterating through i and j, a valid value in the bottom right cell of dp will indicate that a valid path exists that matches s3, so we can just return the contents of that cell.
- Time Complexity: O(N * M) where N is the length of s1 and M is the length of s2
- Space Complexity: O(N * M) for the dp matrix
Javascript Code:
(Jump to: Problem Description || Solution Idea)
var isInterleave = function(s1, s2, s3) {
let n = s1.length, m = s2.length
if (n + m !== s3.length) return false
let dp = Array.from({length: n+2}, () => new Uint8Array(m+2))
dp[0][1] = 1, n++, m++
for (let i = 1; i <= n; i++)
for (let j = 1; j <= m; j++) {
let up = dp[i-1][j] && s1[i-2] === s3[j+i-3],
left = dp[i][j-1] && s2[j-2] === s3[j+i-3]
dp[i][j] = up || left
}
return dp[n][m]
};
Python Code:
(Jump to: Problem Description || Solution Idea)
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
n, m = len(s1) + 1, len(s2) + 1
if n + m - 2 != len(s3): return False
dp = [[0] * (m + 1) for _ in range(n + 1)]
dp[0][1] = 1
for i, j in product(range(1,n+1), range(1,m+1)):
up = dp[i-1][j] and (i < 2 or s1[i-2] == s3[j+i-3])
left = dp[i][j-1] and (j < 2 or s2[j-2] == s3[j+i-3])
dp[i][j] = up or left
return dp[-1][-1]
Java Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int n = s1.length() + 1, m = s2.length() + 1;
char[] sc1 = s1.toCharArray(), sc2 = s2.toCharArray(), sc3 = s3.toCharArray();
if (n + m - 2 != s3.length()) return false;
boolean[][] dp = new boolean[n+1][m+1];
dp[0][1] = true;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
boolean up = dp[i-1][j] && (i < 2 || sc1[i-2] == sc3[j+i-3]),
left = dp[i][j-1] && (j < 2 || sc2[j-2] == sc3[j+i-3]);
dp[i][j] = up || left;
}
return dp[n][m];
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n = s1.length() + 1, m = s2.length() + 1;
if (n + m - 2 != s3.length()) return false;
vector<vector<bool>> dp(n+1, vector<bool>(m+1, false));
dp[0][1] = true;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
bool up = dp[i-1][j] && (i < 2 || s1[i-2] == s3[j+i-3]),
left = dp[i][j-1] && (j < 2 || s2[j-2] == s3[j+i-3]);
dp[i][j] = up || left;
}
return dp[n][m];
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-06-03T04:25:43+00:00) Solution: Interleaving String. Retrieved from https://www.scien.cx/2021/06/03/solution-interleaving-string/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.