牛客网：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:
@cache
def dfs(start):
if start == len(s):
return 0
result = dfs(start + 1) + 1
for end in range(start, len(s)):
word = s[start: end + 1]
if word not in dictionary:
continue
result = min(result, dfs(end + 1))
return result
return dfs(0)
细看思路很简单，递归查找并比较所留最少字符的答案；
基于此思路，开启了Go语言的模仿：
第一反应，按照Up主的思路，直接dfs递归查找，结果当场TLE，debug发现，在回溯每个dfs，都会查找一次重复数据，于是开始剪枝优化
func minExtraChar(s string, dictionary []string) int {
var dfs func(start int) int
dfs = func(start int) int {
if start == len(s) {
return 0
}
result := dfs(start+1) + 1
for 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) int
dfs = func(start int) int {
if start == len(s) {
return 0
}
if val, ok := cache[start]; ok {
return val
}
result := dfs(start+1) + 1
for end := start; end < len(s); end++ {
word := s[start : end+1]
found := false
for _, w := range dictionary {
if word == w {
found = true
break
}
}
if !found {
continue
}
result = min(result, dfs(end+1))
}
cache[start] = result
return result
}
return dfs(0)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
