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 的技巧優化到接近線性?