代码随想录算法训练营第45天 | 115.不同的子序列、583. 两个字符串的删除操作、72. 编辑距离

115.不同的子序列

题目链接：. - 力扣（LeetCode）

func numDistinct(s string, t string) int {dp:=make([][]int,len(s)+1)arr:=make([]int,len(t)+1)arr[0]=1for i:=range dp{dp[i]=append([]int{},arr...)}//dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。for i:=1;i<len(dp);i++{for j:=1;j<len(dp[i]);j++{if s[i-1]==t[j-1]{dp[i][j]=dp[i-1][j-1]+dp[i-1][j]}else{dp[i][j]=dp[i-1][j]}}}return dp[len(s)][len(t)]
}

583. 两个字符串的删除操作

题目链接：. - 力扣（LeetCode）

func minDistance(word1 string, word2 string) int {dp:=make([][]int,len(word1)+1)arr:=make([]int,len(word2)+1)for i:=range dp{dp[i]=append([]int{},arr...)}for i:=range dp[0]{dp[0][i]=i}for i:=range dp{dp[i][0]=i}// dp[i][j]: word1 i,word2 j 所需的最小步数for i:=1;i<len(dp);i++{for j:=1;j<len(dp[i]);j++{if word1[i-1]==word2[j-1]{dp[i][j]=dp[i-1][j-1]}else{dp[i][j]=min(dp[i-1][j-1]+1,min(dp[i][j-1],dp[i-1][j]))+1}}}return dp[len(word1)][len(word2)]
}

72. 编辑距离

题目链接：. - 力扣（LeetCode）

func minDistance(word1 string, word2 string) int {dp:=make([][]int,len(word1)+1)arr:=make([]int,len(word2)+1)for i:=range dp{dp[i]=append([]int{},arr...)}for i:=range dp[0]{dp[0][i]=i}for i:=range dp{dp[i][0]=i}// dp[i][j]: word1 i,word2 j 所需的最小步数for i:=1;i<len(dp);i++{for j:=1;j<len(dp[i]);j++{if word1[i-1]==word2[j-1]{dp[i][j]=dp[i-1][j-1]}else{dp[i][j]=min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1}}}return dp[len(word1)][len(word2)]
}