给定两个字符串s1和s2返回使两个字符串相等所需删除字符的ascll值的最小和用go写
这个问题可以使用动态规划的方法来解决。
首先,我们定义一个二维数组dp,其中dp[i][j]表示将字符串s1的前i个字符和字符串s2的前j个字符相等所需要删除的字符的ascll值的最小和。
然后,我们可以根据以下几种情况来计算dp[i][j]的值:
- 如果s1[i-1]等于s2[j-1],那么dp[i][j] = dp[i-1][j-1],因为不需要删除任何字符。
- 如果s1[i-1]不等于s2[j-1],那么我们可以选择删除s1[i-1]或者s2[j-1],所以dp[i][j] = min(dp[i-1][j] + int(s1[i-1]), dp[i][j-1] + int(s2[j-1]))。
最后,dp[len(s1)][len(s2)]就是最终的答案。
下面是使用Go语言实现的代码:
func minimumDeleteSum(s1 string, s2 string) int {
m, n := len(s1), len(s2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
dp[i][0] = dp[i-1][0] + int(s1[i-1])
}
for j := 1; j <= n; j++ {
dp[0][j] = dp[0][j-1] + int(s2[j-1])
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if s1[i-1] == s2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
dp[i][j] = min(dp[i-1][j]+int(s1[i-1]), dp[i][j-1]+int(s2[j-1]))
}
}
}
return dp[m][n]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
这样,我们就可以通过调用minimumDeleteSum函数来获取使两个字符串相等所需删除字符的ascll值的最小和
原文地址: https://www.cveoy.top/t/topic/iSiQ 著作权归作者所有。请勿转载和采集!