本文主要是介绍LeetCode每日一题 | 2707. 字符串中的额外字符，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 题目描述
- 问题分析
- 程序代码
题目描述
原题链接
给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串，每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。
请你采取最优策略分割 s ，使剩下的字符 最少 。
问题分析
仔细观察这道题可以发现，可以转化成背包问题。
状态定义：dp[i]表示s[0...i-1]的所有分割策略中，剩下字符的最小值。
状态计算：遍历单词字典中的所有字符串（看成物品），若字典中字符串v的长度t小于等于字符串s（物品体积小于背包体积），则计算分割出该字符串v是否能使得剩下的字符数量更少，即dp[i] = min(dp[i], dp[i - t])。
程序代码
func minExtraChar(s string, dictionary []string) int {n := len(s)dp := make([]int, n + 1)for i := 1; i <= n; i++ {dp[i] = dp[i-1] + 1for _, v := range dictionary {t := len(v)if t <= i && s[i-t : i] == v {dp[i] = min(dp[i], dp[i-t])}}}return dp[n]
}
这篇关于LeetCode每日一题 | 2707. 字符串中的额外字符的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
