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:

        @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
}