leetcode 97. 交错字符串
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false
解题思路:
-
首先长度上验是否是两个字符串组合的
-
进一步字符上验证,用一个二维数组行列分别代表s1和s2
-
d[i][j]表示s3匹配的字符串s1前i个字符字符串s2前j个字,初始化s1前0个字符字符串s2前0个字符匹配
-
一开始只匹配s1或s2的字符时,首先前j-1个是匹配上的,判断第j个字符相同,则前j个字符匹配,i一样
-
同时匹配s1,s2中的字符,s2前j-1个字符相同和字符串中第j个字符相同,s1前i-1个字符相同和字符串中第i个字符相同
C/C++题解:
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if (s1.size() + s2.size() != s3.size())
return false;
//d[i][j]表示s3匹配的字符串s1前i个字符字符串前j个字符
vector<vector<char>> dp(s1.size() + 1, vector<char>(s2.size() + 1, 0));
for (int i = 0; i < s1.size() + 1; i++){
for (int j = 0; j < s2.size() + 1; j++){
if (i == 0 && j == 0)//匹配0个字符时初始化1
dp[0][0] = 1;
else if (i == 0)//只匹配后一个字符串中的字符
//最终返回true,则字符串s2前j-1个字符相同和字符串中第j个字符相同
dp[i][j] = dp[i][j - 1] && s2[j - 1] == s3[j - 1];
else if (j == 0)//只匹配前一个字符串中的字符
//最终返回true,则字符串s1前i-1个字符相同和字符串中第i个字符相同
dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[i - 1];
else{//同时匹配s1,s2中的字符
//s2前j-1个字符相同和字符串中第j个字符相同,s1前i-1个字符相同和字符串中第i个字符相同
dp[i][j] = (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1])
|| (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]);} }
}//最后s2整个字符串和s1整个字符串匹配情况
return dp[s1.size()][s2.size()];}};
Debug结果:
Java题解:
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length())
return false;
//d[i][j]表示s3匹配的字符串s1前i个字符字符串前j个字符
boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
for (int i = 0; i < s1.length() + 1; i++){
for (int j = 0; j < s2.length() + 1; j++){
if (i == 0 && j == 0)//匹配0个字符时初始化1
dp[0][0] = true;
else if (i == 0)//只匹配后一个字符串中的字符
//最终返回true,则字符串s2前j-1个字符相同和字符串中第j个字符相同
dp[i][j] = dp[i][j - 1] && (s2.charAt(j - 1)==(s3.charAt(j - 1)));
else if (j == 0)//只匹配前一个字符串中的字符
//最终返回true,则字符串s1前i-1个字符相同和字符串中第i个字符相同
dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1)==(s3.charAt(i - 1));
else{//同时匹配s1,s2中的字符
//s2前j-1个字符相同和字符串中第j个字符相同,s1前i-1个字符相同和字符串中第i个字符相同
dp[i][j] = (dp[i][j - 1] && s2.charAt(j - 1)==(s3.charAt(i + j - 1)))
|| (dp[i - 1][j] && s1.charAt(i - 1)==(s3.charAt(i +j - 1)));}}
}//最后s2整个字符串和s1整个字符串匹配情况
return dp[s1.length()][s2.length()]; }}
Debug结果:
Python题解:
class Solution(object):
def isInterleave(self, s1, s2, s3):
""":type s1: str:type s2: str:type s3: str:rtype: bool"""
if len(s1) + len(s2) != len(s3): return False;
#d[i][j]表示s3匹配的字符串s1前i个字符字符串前j个字符
dp = [[False for _ in range(len(s2)+1)] for _ in range(len(s1)+1)]
for i in range(len(s1)+1):
for j in range(len(s2)+1):
if i == 0 and j == 0: #匹配0个字符时初始化1
dp[0][0] = True
elif i == 0: #只匹配后一个字符串中的字符
#最终返回true,则字符串s2前j-1个字符相同和字符串中第j个字符相同
dp[i][j] = dp[i][j - 1] and s2[j - 1] == s3[j - 1]
elif j == 0: #只匹配前一个字符串中的字符
#最终返回true,则字符串s1前i-1个字符相同和字符串中第i个字符相同
dp[i][j] = dp[i - 1][j] and s1[i - 1] == s3[i - 1]
else: #同时匹配s1,s2中的字符
#s2前j-1个字符相同和字符串中第j个字符相同,s1前i-1个字符相同和字符串中第i个字符相同
dp[i][j] = (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
or (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1])
#最后s2整个字符串和s1整个字符串匹配情况
return dp[len(s1)][len(s2)]
Debug结果:
更多题解移步公众号免费获取