MediumRating 2082

3291. Minimum Number of Valid Strings to Form Target I

arraystringbinary-searchdynamic-programmingtriesegment-treerolling-hashstring-matchinghash-function

解題說明

Minimum Number of Valid Strings to Form Target I

題目描述：給定一組字串 words 和目標字串 target。一個「有效字串」是 words 中任一字串的前綴。求最少需要多少個有效字串可以串接成 target，若不可能則回傳 -1。

解題思路：用 Trie 儲存所有 words 的前綴。定義 dp[i] 為組成 target[0..i-1] 所需的最少有效字串數。對每個位置 i，在 Trie 中嘗試匹配 target[i..] 的最長前綴。若能匹配到位置 j，則 dp[j+1] = min(dp[j+1], dp[i] + 1) 對所有 i < j+1 <= i+maxMatch。實際上，由於每個位置在 Trie 上最多走 L 步（L 為 words 最長長度），整體時間可控。

C++ 解法

複雜度分析

時間複雜度：O(S + n × L) — 建立 Trie 為 O(S)（S 為 words 總字元數），DP 遍歷目標字串每個位置，每個位置最多在 Trie 上走 L 步。

空間複雜度：O(S + n) — Trie 大小 O(S)，DP 陣列 O(n)。

虛擬碼

1. Build Trie from all words
2. Initialize dp[0] = 0, dp[1..n] = INF
3. For i = 0 to n-1:
   a. If dp[i] == INF, skip
   b. Walk Trie matching target[i], target[i+1], ...
   c. For each matched position j: dp[j+1] = min(dp[j+1], dp[i] + 1)
   d. Stop when Trie has no matching child
4. Return dp[n] or -1 if INF

其他解法

Aho-Corasick + DP O(S + n)：建立 Aho-Corasick 自動機，在自動機上沿 target 走一遍，用 suffix link 快速找到所有可匹配的前綴。可將內層迴圈優化到均攤 O(1)。

Rolling Hash + 二分搜尋 O(n log L)：對每個位置 i 二分搜尋最長可匹配前綴的長度。用 rolling hash 判斷 target[i..i+len-1] 是否為某個 word 的前綴。需要預處理所有 words 的前綴 hash。

延伸思考

如果有效字串不限於前綴，也可以是任意子字串，問題如何改變？
如果要輸出具體的分割方案（不只是最少數量），如何追蹤路徑？
當 target 長度很大（10⁵）時，如何使用 Part II 的技巧優化到接近線性？

Minimum Number of Valid Strings to Form Target I — CaffeCode