解題說明
Partition String
題目描述:給定一個字串 s 和一組模式字串 pattern,將 s 從左到右劃分為若干段。每一段的劃分規則:從當前位置開始,找到在 pattern 中出現的最長前綴作為一段。若當前字元無法匹配任何模式的起始,則該字元單獨作為一段。回傳劃分後的段數。
解題思路:使用 Trie(前綴樹)來高效匹配模式。首先將所有模式字串插入 Trie。然後從字串 s 的開頭開始,在 Trie 中進行最長匹配:沿著 Trie 向下走,記錄最後一次到達終端節點的位置,即為最長匹配。若沒有任何匹配,跳過一個字元。每次匹配後,從匹配結束的下一個位置繼續。
C++ 解法
複雜度分析
時間複雜度:O(L + n * M) — 建 Trie O(L)(L 為所有模式的總長度),匹配過程中每個位置最多走 M 步(M 為最長模式長度),但攤銷後接近 O(n)。
空間複雜度:O(L * 26) — Trie 節點數最多 O(L),每個節點 26 個指標。
虛擬碼
1. Build a Trie from all pattern strings 2. Initialize pointer i = 0, parts = 0 3. While i < len(s): a. Walk Trie from root, following s[i], s[i+1], ... b. Record the position of the last complete pattern match (lastMatch) c. Increment parts d. If lastMatch found: set i = lastMatch e. Else: set i = i + 1 (skip one char) 4. Return parts
其他解法
雜湊集合 O(n * M²):將所有模式存入 HashSet,對每個位置嘗試所有可能長度的子字串查找最長匹配。簡單但慢。
Aho-Corasick 自動機 O(n + L):建立 AC 自動機可以在 O(n) 時間內找到所有模式的出現位置,然後用貪心選擇最長匹配。適合模式數量非常大的情況。
延伸思考
- 如果要求劃分出的段數最少,貪心(最長匹配)是否一定是最優策略?
- 若模式可以重疊(例如 "ab" 和 "abc" 都在模式中),如何確保正確選擇最長匹配?
- 若字串和模式都很長(10^6),如何在記憶體受限的環境下優化 Trie?