题目描述
给你一个下标从 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] + 1
for _, 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]
}