97. Interleaving String
給定三個字符串 s1、s2 和 s3，判斷 s3 是否由 s1 和 s2 交錯組成。
兩個字符串 s 和 t 的交錯是一種配置，其中 s 和 t 被劃分為 n 和 m 個子串，滿足：
s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 交錯可以是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或 t1 + s1 + t2 + s2 + t3 + s3 + ... 注意：a + b 是字符串 a 和 b 的連接。
範例：
輸入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 輸出：true 解釋：一種獲得 s3 的方式是： 將 s1 分割為 s1 = "aa" + "bc" + "c"，將 s2 分割為 s2 = "dbbc" + "a"。 將這兩個分割交錯，我們得到 "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac"。 由於 s3 可以通過交錯 s1 和 s2 獲得，因此我們返回 true。
Python
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
len1, len2, len3 = len(s1), len(s2), len(s3)
# Early return if the length doesn't match the requirement
if len1 + len2 != len3:
return False
# Initialize a 2D DP table with False values
dp = [[False] * (len2 + 1) for _ in range(len1 + 1)]
# Initial condition: an empty s1 and s2 can form an empty s3
dp[0][0] = True
# Fill the first row (using only s2 to match s3)
for j in range(1, len2 + 1):
dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
# Fill the first column (using only s1 to match s3)
for i in range(1, len1 + 1):
dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
# Fill the rest of the DP table
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i-1 + j]) or \
(dp[i][j-1] and s2[j-1] == s3[i + j-1])
return dp[len1][len2]
16.72MB, 45ms
C++
#include <vector>
#include <string>
class Solution {
public:
bool isInterleave(std::string s1, std::string s2, std::string s3) {
int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
// If the combined lengths of s1 and s2 do not match s3, return false
if (len1 + len2 != len3) {
return false;
}
// Create a 2D vector for the DP table
std::vector<std::vector<bool>> dp(len1 + 1, std::vector<bool>(len2 + 1, false));
// Initial condition: an empty s1 and s2 can form an empty s3
dp[0][0] = true;
// Initialize the first column (using s1 to match s3)
for (int i = 1; i <= len1; ++i) {
dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1];
}
// Initialize the first row (using s2 to match s3)
for (int j = 1; j <= len2; ++j) {
dp[0][j] = dp[0][j-1] && s2[j-1] == s3[j-1];
}
// Fill in the rest of the DP table
for (int i = 1; i <= len1; ++i) {
for (int j = 1; j <= len2; ++j) {
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]);
}
}
// The bottom-right corner of the DP table holds the answer
return dp[len1][len2];
}
};
8.15MB, 6ms
Javascript
/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
var isInterleave = function(s1, s2, s3) {
const len1 = s1.length, len2 = s2.length, len3 = s3.length;
// Check if the total length of s1 and s2 equals the length of s3
if (len1 + len2 !== len3) {
return false;
}
// Create a 2D array for the DP table
const dp = Array.from({ length: len1 + 1 }, () => Array(len2 + 1).fill(false));
// Initial condition: an empty s1 and s2 can form an empty s3
dp[0][0] = true;
// Initialize the first row (using only s2 to match s3)
for (let j = 1; j <= len2; j++) {
dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[j - 1];
}
// Initialize the first column (using only s1 to match s3)
for (let i = 1; i <= len1; i++) {
dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1];
}
// Fill the DP table
for (let i = 1; i <= len1; i++) {
for (let j = 1; j <= len2; j++) {
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]);
}
}
// Return the value in the bottom-right corner of the DP table
return dp[len1][len2];
};
53.36MB, 77ms
