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]題目描述:
給定一個字串陣列 words(所有字串等長)和一個目標字串 target。可以用以下規則組成 target:從左到右逐字元構建,每次選擇 words 中任意一個字串的第 k 列字元來匹配 target 的下一個字元,且使用的列索引必須嚴格遞增。求有多少種方式組成 target(答案對 10⁹+7 取模)。
解題思路:
freq[j][c] 表示 words 中第 j 列出現字元 c 的次數。dp[i][j] = 用前 j 列去匹配 target 的前 i 個字元的方法數。dp[i][j] = dp[i][j-1]dp[i][j] += dp[i-1][j-1] * freq[j][target[i-1]]時間複雜度: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)。
二維 DP O(m·k) 空間:直接維護 dp[i][j] 的二維表格,不做滾動優化。邏輯更清晰但空間消耗大,當 k 和 m 都很大時可能超出記憶體限制。
記憶化搜索 O(m·k):dfs(i, j) 表示從第 j 列開始匹配 target[i:] 的方法數。本質相同但使用遞迴棧,可能在深度很大時造成棧溢出。