Re: [閒聊] 每日leetcode已回收
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]
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.34.11 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718375648.A.322.html
討論串 (同標題文章)
完整討論串 (本文為第 361 之 1548 篇)：