🔗 🟡 2707. Extra Characters in a String 1736

tags: Biweekly Contest 105 陣列(Array) 字串(String) 動態規劃(Dynamic Programming) 記憶化搜尋(Memoization) 雜湊表(Hash Table) 字典樹(Trie)

題意

給定一個下標從 00 開始的字串 ss 和一個單字字典 dictionarydictionary。你需要將 ss 分割成一個或多個不重疊的子字串，每個子字串均存在於字典中。但 ss 中可能會有一些額外的字元未出現在任何子字串中。

返回在最佳分割 ss 的情況下，剩餘的 最少 額外字元數。

思路：動態規劃(Dynamic Programming) + 雜湊表(Hash Table) / 字典樹(Trie)

方法一：動態規劃(Dynamic Programming) + 雜湊表(Hash Table)

首先定義問題，令 dfs(i)dfs(i) 表示從第 ii 個字元開始，所得到的最少獨立字元數，即子字串 s[i:]s[i:] 中，需要添加的最少額外字元數量。由於可以將問題分解成重複的子問題，因此可以使用 動態規劃(Dynamic Programming) 來解決。

根據我們對問題的定義，則 dfs(i)dfs(i) 可以從以下兩種來源中轉移，從中取最小值：

  • 若選擇 s[i]s[i] 作為獨立字元，則 dfs(i)=dfs(i+1)+1dfs(i) = dfs(i+1) + 1
  • 枚舉 j∈[i,n−1]j \in [i, n-1]，若 s[i:j+1]s[i:j+1] 在字典中，則 dfs(i)=min⁡j∈[i,n−1]s[i:j+1]∈dictionary(dfs(j+1))dfs(i) = \displaystyle\min_{\substack{j \in [i, n-1] \\ s[i:j+1] \in dictionary}} \left(dfs(j+1)\right)

這裡使用 記憶化搜尋(Memoization) 來實現動態規劃。

而檢查子字串 s[i:j+1]s[i:j+1] 是否在字典中，可以使用 雜湊表(Hash Table) 保存字典中的單字後來查找。

複雜度分析

  • 時間複雜度：O(n3+L)\mathcal{O}(n^3 + L)，其中 LL 為字典中所有單字的總長度，nn 為字串 ss 的長度。
    • 預處理字典中的單字，需要 O(L)O(L) 的時間複雜度。
    • 總共有 nn 個位置(狀態)，對於每個狀態需要枚舉 O(n)O(n) 個可能的子字串，每個子字串需要 O(n)O(n) 的時間複雜度來檢查是否在字典中。
  • 空間複雜度：O(n+L)\mathcal{O}(n + L)
    • 需要 O(L)O(L) 的空間複雜度來保存字典中的單字。
    • 總共有 nn 個狀態，需要 O(n)O(n) 的空間複雜度來保存每個狀態的結果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        n = len(s)
        words = set(dictionary)
        
        # 從第 i 個位置開始，所得到的獨立字元數 
        @cache # Memoization
        def dfs(i: int):
            if i >= n:
                return 0
            res = dfs(i + 1) + 1 # 不選，即第 i 個字元為獨立字元的情況
            for j in range(i, n): # 枚舉以第 i 個字元開頭的字
                if s[i:j+1] in words: # 如果該字串在字典中
                    res = min(res, dfs(j+1)) # 選擇該字串，並遞迴計算剩餘字串的獨立字元數
            return res
        return dfs(0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        int n = s.size();
        unordered_set<string> words(dictionary.begin(), dictionary.end());
        vector<int> memo(n, -1);
        function<int(int)> dfs = [&](int i) -> int {
            if (i >= n) return 0;
            int& res = memo[i];
            if (res != -1) return res;
            res = dfs(i + 1) + 1; // 不選，即第 i 個字元為獨立字元的情況
            for (int j = i; j < n; ++j) {
                if (words.count(s.substr(i, j - i + 1))) {
                    res = min(res, dfs(j + 1));
                }
            }
            return res;
        };
        return dfs(0);
    }
};

方法二：動態規劃(Dynamic Programming) + 字典樹(Trie)

在方法一中，我們使用雜湊表(Hash Table)來檢查子字串是否在字典中。然而，雜湊表的查找一個單字的時間複雜度為 O(x)\mathcal{O}(x)，其中 xx 為子字串的長度，且當我們從 s[i:j]s[i:j] 轉移到 s[i:j+1]s[i:j+1] 時，又需要重新計算子字串的雜湊值。故可以使用 字典樹(Trie) 來優化查找的時間複雜度。

為此我們首先要創建一個字典樹，將字典中的單字插入到字典樹中，並標記單詞的結尾。在這裡不多贅述字典樹的實現，可以參考程式碼或是自行查詢相關資料。

在轉移時，我們從 s[i]s[i] 開始，在字典樹中查找匹配的字串。如果當前字元不在字典樹的子節點中，則停止繼續查找。若找到一個在字典中的單字，即 node.is_end == true ，則可以更新結果。此外，若當前字元 s[j]s[j] 不在字典樹的子節點中，則不用繼續往下找，可以直接跳出迴圈。

除了檢查子字串是否在字典中的方式，其餘部分與方法一大致相同。

複雜度分析

  • 時間複雜度：O(n2+L)\mathcal{O}(n^2 + L)，其中 LL 為字典中所有單字的總長度，nn 為字串 ss 的長度。
    • 構建字典樹需要 O(L)O(L) 的時間複雜度。
    • 總共有 nn 個位置(狀態)，對於每個狀態，需要 O(n)O(n) 的時間複雜度來查找所有子字串是否在字典中。
  • 空間複雜度：O(n+∣Σ∣L)\mathcal{O}(n + |\Sigma|L)，其中 ∣Σ∣|\Sigma| 為字典樹中所有可能的字元數，本題中為 2626。
    • 需要 O(L)O(L) 的空間複雜度來保存字典樹中的單字作為節點，而每個節點需要 ∣Σ∣|\Sigma| 的空間來保存指針。如果使用雜湊表來保存子節點，則需要 O(L)O(L) 的空間複雜度。
    • 總共有 nn 個狀態，故總共需要 O(n)O(n) 的空間複雜度來保存每個狀態的結果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class TrieNode:
    def __init__(self) -> None:
        self.child = {}
        self.is_end = False

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        n = len(s)

        root = TrieNode()
        for word in dictionary:
            node = root
            for ch in word:
                if ch not in node.child:
                    node.child[ch] = TrieNode()
                node = node.child[ch]
            node.is_end = True
        
        @cache
        def dfs(i: int):
            if i >= n:
                return 0
            res = dfs(i + 1) + 1 # 不選，即第 i 個字元為獨立字元的情況
            node = root
            for j in range(i, n):
                ch = s[j]
                if ch not in node.child: # 當前字元不在字典樹中，不用繼續往下找
                    break
                node = node.child[ch]
                if node.is_end: # 選，s[i:j+1] 在字典中
                    res = min(res, dfs(j + 1))
            return res
        return dfs(0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class TrieNode {
public:
    vector<TrieNode*> child;
    bool is_end;
    TrieNode() {
        child = vector<TrieNode*>(26, nullptr);
        is_end = false;
    }
};

class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        int n = s.size();

        TrieNode* root = new TrieNode();
        for (const string& word : dictionary) {
            TrieNode* node = root;
            for (char ch : word) {
                if (node->child[ch - 'a'] == nullptr) {
                    node->child[ch - 'a'] = new TrieNode();
                }
                node = node->child[ch - 'a'];
            }
            node->is_end = true;
        }

        vector<int> memo(n, -1);
        function<int(int)> dfs = [&](int i) -> int {
            if (i >= n) return 0;
            int& res = memo[i];
            if (res != -1) return res;
            res = dfs(i + 1) + 1; // 不選，即第 i 個字元為獨立字元的情況
            TrieNode* node = root;
            for (int j = i; j < n; ++j) {
                if (node->child[s[j] - 'a'] == nullptr) break; // 當前字元不在字典樹中，不用繼續往下找
                node = node->child[s[j] - 'a'];
                if (node->is_end) res = min(res, dfs(j + 1)); // 選，s[i:j+1] 在字典中
            }
            return res;
        };
        return dfs(0);
    }
};

寫在最後

Cover photo is remixed from @吃肥皂泡泡, thanks for their work!

感覺見過很多次，特別是字典樹優化的版本。