2707. Extra Characters in a String
给一个字串s和字串矩阵dictionary
把s分成一个或多个不重叠的子字串
这些子字串为dictionary里的字串
可能会有一些字符没有出现在任何子字串
请回传没有出现在子字串的字符最少的数目
思路:
用hash table+dp
先用字首字母去记录每个dictionary里的字串
假设s的长度为n
建立一个n+1的dp矩阵
dp[i+1]为到s[i]时match到的字符数量
去搜寻hash table有没有s[i]开头match的字串
有的话dp[i+length]=max(dp[i+length],dp[i]+length)
接着对于dp[i]=max(dp[i],dp[i+1])
最后回传n-dp[n]就是答案了
golang code :
func minExtraChar(s string, dictionary []string) int {
rec := [26][]string{}
for _, val := range dictionary {
idx := int(val[0] - 'a')
rec[idx] = append(rec[idx], val)
}
n := len(s)
dp := make([]int, n+1)
for i := 0; i < n; i++ {
idx := int(s[i] - 'a')
for _, val := range rec[idx] {
length := len(val)
if i+length <= n && s[i:i+length] == val {
dp[i+length] = max(dp[i+length], dp[i]+length)
}
}
dp[i+1] = max(dp[i], dp[i+1])
}
return n - dp[n]
}