HardRating 2082
1639. Number of Ways to Form a Target String Given a Dictionary
arraystringdynamic-programming
解題說明
Number of Ways to Form a Target String Given a Dictionary
題目描述：
給定一個字串陣列 words（所有字串等長）和一個目標字串 target。可以用以下規則組成 target：從左到右逐字元構建，每次選擇 words 中任意一個字串的第 k 列字元來匹配 target 的下一個字元，且使用的列索引必須嚴格遞增。求有多少種方式組成 target（答案對 10⁹+7 取模）。
解題思路：
- 預處理頻率表：建立
freq[j][c]表示 words 中第 j 列出現字元 c 的次數。 - DP 定義：
dp[i][j]= 用前 j 列去匹配 target 的前 i 個字元的方法數。 - 轉移：
- 不使用第 j 列：
dp[i][j] = dp[i][j-1] - 使用第 j 列匹配 target[i-1]：
dp[i][j] += dp[i-1][j-1] * freq[j][target[i-1]]
- 不使用第 j 列：
- 可以用一維 DP 滾動優化空間。從後往前更新避免覆蓋。
C++ 解法
複雜度分析
時間複雜度：O(n·k + m·k) — 預處理頻率表 O(n·k)，其中 n = words.length、k = 字串長度；DP 遍歷 O(m·k)，其中 m = target.length。
空間複雜度：O(26·k + m) — 頻率表 O(26k)，一維 DP 陣列 O(m)。
虛擬碼
1. Let m = target.length, k = words[0].length
2. Build freq[j][c] = count of char c in column j across all words
3. Initialize dp[0..m] = 0, dp[0] = 1
4. For each column j from 0 to k-1:
a. For each i from min(m, j+1) down to 1:
- c = target[i-1]
- dp[i] = (dp[i] + dp[i-1] * freq[j][c]) % MOD
5. Return dp[m]其他解法
二維 DP O(m·k) 空間：直接維護 dp[i][j] 的二維表格，不做滾動優化。邏輯更清晰但空間消耗大，當 k 和 m 都很大時可能超出記憶體限制。
記憶化搜索 O(m·k)：dfs(i, j) 表示從第 j 列開始匹配 target[i:] 的方法數。本質相同但使用遞迴棧，可能在深度很大時造成棧溢出。
延伸思考
- 如果 words 中的字串長度不一致，該如何調整預處理方式？
- 如果允許同一列被使用多次（列索引非嚴格遞增），DP 轉移如何改變？
- 如何將此方法推廣到二維目標矩陣的匹配問題？