97. Interleaving String
有三个字串s1、s2、s3
请问s3是否能由s1、s2交错组成
交错组成的意思
s=s1+s2+...+sn
t=t1+t2+...+tm
|n-m|<=1
交错组成就是:s1+t1+s2+t2+.... or t1+s1+t2+s2+....
思路:
dp问题
建立一个二维的DP矩阵
其中dp[i][j]纪录s3[0~i+j-1]是否能由s1[0~i-1]+s2[0~j-1]组成
dp[i][j]有3种期况会为true
(1)dp[i-1][j]==true && dp[i][j-1]==true
此时只要s1[i-1]==s3[i+j-1] || s2[j-1]==s3[i+j-1]，dp[i][j]=true
(2)dp[i-1][j]==true
当s2[j-1]==s3[i+j-1]，dp[i][j]=true
(3)dp[i][j-1]=true
当s1[i-1]==s3[i+j+1]，dp[i][j]=true
最后去判断dp[n][m]是不是为true就好
golang code :
func isInterleave(s1 string, s2 string, s3 string) bool {
n,m:=len(s1),len(s2)
if n+m!=len(s3){
return false
}
dp1:=make([]bool,n+1)
dp1[0]=true
for i:=0;i<n;i++{
if s1[i]==s3[i]{
dp1[i+1]=true
}else{
break
}
}
for i:=1;i<=m;i++{
dp2:=make([]bool,n+1)
if dp1[0] && s2[i-1]==s3[i-1]{
dp2[0]=true
}
for j:=1;j<=n;j++{
if dp1[j] && dp2[j-1]{
if s1[j-1]==s3[i+j-1] || s2[i-1]==s3[i+j-1]{
dp2[j]=true
}
}else if dp1[j]{
if s2[i-1]==s3[i+j-1]{
dp2[j]=true
}
}else if dp2[j-1]{
if s1[j-1]==s3[i+j-1]{
dp2[j]=true
}
}
}
dp1=dp2
}
return dp1[n]
}