2707. Extra Characters in a String

Medium

Description

給定字串 s 和字典 dictionary，將 s 拆分成若干子字串，其中一些子字串在字典中。回傳最少的「多餘字元」數量（不在任何字典匹配中的字元）。

Example:

Input: s = “leetscode”, dictionary = [“leet”,“code”,“leetcode”] Output: 1 (拆成 “leet” + “s” + “code”，多餘 1 個字元 “s”)

Intuition#

核心思路：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#

概念: 用 HashSet 儲存字典，對每個位置 i 嘗試所有可能的子字串
時間複雜度: O(n^2 * L) - n 為字串長度，L 為字典中最長詞的長度（substring 比較）
空間複雜度: 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#

概念: 先將字典建成 Trie，DP 時從每個位置向後在 Trie 中走，找到所有匹配的字典詞
時間複雜度: O(n^2 + m) - n^2 為 DP 搜尋，m 為建 Trie 的字典總字元數
空間複雜度: 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]
    }
}

注意：上面 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 讓我們一次遍歷中找到所有以某位置開頭的字典詞
關鍵技巧: DP 轉移有兩種選擇：當前字元作為多餘 dp[i-1]+1，或匹配字典詞 dp[j]；Trie 避免了對每個子字串做獨立的 HashSet 查詢