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