給定字串
s和字典dictionary，將s拆分成若干子字串，其中一些子字串在字典中。回傳最少的「多餘字元」數量（不在任何字典匹配中的字元）。
Example:
Input: s = “leetscode”, dictionary = [“leet”,“code”,“leetcode”] Output: 1 (拆成 “leet” + “s” + “code”，多餘 1 個字元 “s”)
Intuition
TIP
核心思路：DP + Trie——dp[i] 表示前 i 個字元最少的多餘字元數，用 Trie 加速字典匹配。
dp[i]= 字串s[0..i-1]的最少多餘字元數- 轉移：
dp[i] = dp[i-1] + 1（第 i 個字元作為多餘），或找到字典匹配s[j..i-1]則dp[i] = min(dp[i], dp[j]) - 用 HashSet 可以 O(L) 查詢每個子字串，但用 Trie 可以同時檢查所有以某位置結尾的字典詞
Approaches
1. DP + HashSet — O(n^2 * L) / O(n + m)
- Idea: 用 HashSet 儲存字典，對每個位置 i 嘗試所有可能的子字串
- Time:
O(n^2 * L)- n 為字串長度，L 為字典中最長詞的長度（substring 比較） - Space:
O(n + m)- DP 陣列 + HashSet（m 為字典總字元數）
class Solution {
fun minExtraChar(s: String, dictionary: Array<String>): Int {
val dict = dictionary.toHashSet()
val n = s.length
val dp = IntArray(n + 1) { it } // 最壞情況：全是多餘字元
for (i in 1..n) {
dp[i] = dp[i - 1] + 1 // s[i-1] 作為多餘字元
for (j in 0 until i) {
if (s.substring(j, i) in dict) {
dp[i] = minOf(dp[i], dp[j])
}
}
}
return dp[n]
}
}⭐ 2. DP + Trie — O(n^2 + m) / O(n + m)
- Idea: 先將字典建成 Trie，DP 時從每個位置向後在 Trie 中走，找到所有匹配的字典詞
- Time:
O(n^2 + m)- n^2 為 DP 搜尋，m 為建 Trie 的字典總字元數 - Space:
O(n + m)- DP 陣列 + Trie
class Solution {
private class TrieNode {
val children = arrayOfNulls<TrieNode>(26)
var isEnd = false
}
fun minExtraChar(s: String, dictionary: Array<String>): Int {
val root = TrieNode()
// 建 Trie
for (word in dictionary) {
var node = root
for (ch in word) {
val idx = ch - 'a'
if (node.children[idx] == null) {
node.children[idx] = TrieNode()
}
node = node.children[idx]!!
}
node.isEnd = true
}
val n = s.length
val dp = IntArray(n + 1) { it }
for (i in 1..n) {
dp[i] = dp[i - 1] + 1 // s[i-1] 作為多餘字元
// 從位置 i 往前搜尋 Trie
var node = root
for (j in i - 1 downTo 0) {
val idx = s[j] - 'a'
node = node.children[idx] ?: break
if (node.isEnd) {
dp[i] = minOf(dp[i], dp[j])
}
}
}
return dp[n]
}
}WARNING
注意：上面 Trie 版本將字典詞反向插入，或者改為從前往後搜尋。更正確的做法是將字典詞正向插入，然後搜尋時從 j 到 i 正向走 Trie：
class Solution {
private class TrieNode {
val children = arrayOfNulls<TrieNode>(26)
var isEnd = false
}
fun minExtraChar(s: String, dictionary: Array<String>): Int {
val root = TrieNode()
for (word in dictionary) {
var node = root
for (ch in word) {
val idx = ch - 'a'
if (node.children[idx] == null) {
node.children[idx] = TrieNode()
}
node = node.children[idx]!!
}
node.isEnd = true
}
val n = s.length
val dp = IntArray(n + 1) { it }
for (i in 0 until n) {
dp[i + 1] = minOf(dp[i + 1], dp[i] + 1)
// 從位置 i 向後在 Trie 中走
var node = root
for (j in i until n) {
val idx = s[j] - 'a'
node = node.children[idx] ?: break
if (node.isEnd) {
dp[j + 1] = minOf(dp[j + 1], dp[i])
}
}
}
return dp[n]
}
}🔑 Takeaways
- Pattern: DP + Trie 加速子字串匹配——Trie 讓我們一次遍歷中找到所有以某位置開頭的字典詞
- Key trick: DP 轉移有兩種選擇：當前字元作為多餘
dp[i-1]+1，或匹配字典詞dp[j]；Trie 避免了對每個子字串做獨立的 HashSet 查詢