2021-06-11：给定两个字符串s1和s2，问s2最少删除多少字符可以成为s1的子串？ 比如 s1 = “abcde”，s2 = “axbc”。
福大大 答案2021-06-11：
解法一
求出str2所有的子序列，然后按照长度排序，长度大的排在前面。
然后考察哪个子序列字符串和s1的某个子串相等(KMP)，答案就出来了。
分析：
因为题目原本的样本数据中，有特别说明s2的长度很小。所以这么做也没有太大问题，也几乎不会超时。
但是如果某一次考试给定的s2长度远大于s1，这么做就不合适了。
str1长度为N，str2长度为M。时间复杂度：O(2的M次方*N)。
解法二
生成所有s1的子串
然后考察每个子串和s2的编辑距离(假设编辑距离只有删除动作且删除一个字符的代价为1)
如果s1的长度较小，s2长度较大，这个方法比较合适。
时间复杂度：O(N * M平方)。
代码用golang编写。代码如下：
package main
import (
"fmt"
"sort"
"strings"
)
func main() {
s1 := "abcde"
s2 := "axbc"
ret1 := minCost1(s1, s2)
ret3 := minCost3(s1, s2)
fmt.Println(ret1, ret3)
}
// 题目：
// 给定两个字符串s1和s2，问s2最少删除多少字符可以成为s1的子串？
// 比如 s1 = "abcde"，s2 = "axbc"
// 返回 1
// 解法一
// 求出str2所有的子序列，然后按照长度排序，长度大的排在前面。
// 然后考察哪个子序列字符串和s1的某个子串相等(KMP)，答案就出来了。
// 分析：
// 因为题目原本的样本数据中，有特别说明s2的长度很小。所以这么做也没有太大问题，也几乎不会超时。
// 但是如果某一次考试给定的s2长度远大于s1，这么做就不合适了。
func minCost1(s1 string, s2 string) int {
s2SubsVal := make([]string, 0)
s2Subs := &s2SubsVal
process(s2, 0, "", s2Subs)
//s2Subs.sort(new LenComp());
sort.Slice(*s2Subs, func(i, j int) bool {
return len((*s2Subs)[i]) > len((*s2Subs)[j])
})
for _, str := range *s2Subs {
if strings.Index(s1, str) != -1 { // indexOf底层和KMP算法代价几乎一样，也可以用KMP代替
return len(s2) - len(str)
}
}
return len(s2)
}
func process(str2 string, index int, path string, list *[]string) {
if index == len(str2) {
*list = append(*list, path)
return
}
process(str2, index+1, path, list)
pathbytes := []byte(path)
pathbytes = append(pathbytes, str2[index])
process(str2, index+1, string(pathbytes), list)
}
// 解法二的优化
func minCost3(s1 string, s2 string) int {
if len(s1) == 0 || len(s2) == 0 {
return len(s2)
}
M := len(s2)
N := len(s1)
dp := make([][]int, M)
for i := 0; i < M; i++ {
dp[i] = make([]int, N)
}
ans := M
for start := 0; start < N; start++ { // 开始的列数
if s2[0] != s1[start] {
dp[0][start] = M
}
for row := 1; row < M; row++ {
if s2[row] == s1[start] || dp[row-1][start] != M {
dp[row][start] = row
} else {
dp[row][start] = M
}
}
ans = getMin(ans, dp[M-1][start])
// 以上已经把start列，填好
// 以下要把dp[...][start+1....N-1]的信息填好
// start...end end - start +2
for end := start + 1; end < N && end-start < M; end++ {
// 0... first-1 行 不用管
first := end - start
if s2[first] == s1[end] && dp[first-1][end-1] == 0 {
} else {
dp[first][end] = M
}
for row := first + 1; row < M; row++ {
dp[row][end] = M
if dp[row-1][end] != M {
dp[row][end] = dp[row-1][end] + 1
}
if dp[row-1][end-1] != M && s2[row] == s1[end] {
dp[row][end] = getMin(dp[row][end], dp[row-1][end-1])
}
}
ans = getMin(ans, dp[M-1][end])
}
}
return ans
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
执行结果如下：
