2707. 字符串中的额外字符

本文主要是介绍2707. 字符串中的额外字符，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

牛客网：https://leetcode.cn/problems/extra-characters-in-a-string/description/?envType=daily-question&envId=2024-01-09

官方解题思路为动态规划或字典数优化；
这里引入Up主的解题思路（递归）

哔哩哔哩：https://www.bilibili.com/video/BV1Ee41127LX/?spm_id_from=333.337.search-card.all.click&vd_source=f385259e95f72c4536cc27a3528bd922

Up主采用python3代码过题：

class Solution:def minExtraChar(self, s: str, dictionary: List[str]) -> int:@cachedef dfs(start):if start == len(s):return 0result = dfs(start + 1) + 1for end in range(start, len(s)):word = s[start: end + 1]if word not in dictionary:continueresult = min(result, dfs(end + 1))return resultreturn dfs(0)

细看思路很简单，递归查找并比较所留最少字符的答案；
基于此思路，开启了Go语言的模仿：
第一反应，按照Up主的思路，直接dfs递归查找，结果当场TLE，debug发现，在回溯每个dfs，都会查找一次重复数据，于是开始剪枝优化

func minExtraChar(s string, dictionary []string) int {var dfs func(start int) intdfs = func(start int) int {if start == len(s) {return 0}result := dfs(start+1) + 1for end := start; end < len(s); end++ {word := s[start : end+1]for _, dic := range dictionary {if word != dic {continue}result = min(result, dfs(end+1))}}return result}return dfs(0)
}

AC代码：

func minExtraChar(s string, dictionary []string) int {cache := make(map[int]int)var dfs func(int) intdfs = func(start int) int {if start == len(s) {return 0}if val, ok := cache[start]; ok {return val}result := dfs(start+1) + 1for end := start; end < len(s); end++ {word := s[start : end+1]found := falsefor _, w := range dictionary {if word == w {found = truebreak}}if !found {continue}result = min(result, dfs(end+1))}cache[start] = resultreturn result}return dfs(0)
}func min(a, b int) int {if a < b {return a}return b
}