Description
給定一組等長字串
words和一個目標字串target。每一步你可以選擇words中任一字串的某個位置的字元來匹配target的下一個字元，但選完後該位置及之前的所有位置都不能再使用。回傳組成target的方式數（對 10^9+7 取餘）。
Example:
Input: words = [“acca”,“bbbb”,“caca”], target = “aba” Output: 6
Intuition#
先統計每個位置各字元的出現次數，再用 DP 計算匹配 target 的方式數。
- 預處理
freq[j][c]：所有 words 在位置j出現字元c的次數 dp[i][j]：用前j個位置匹配target的前i個字元的方式數- 對每個位置
j，可以選擇用它匹配target[i]（乘以頻率）或跳過
Approaches#
1: 2D DP#
- 概念:
dp[i][j]表示target的前i個字元用 words 的前j個位置匹配的方式數。 - 時間複雜度:
O(m * n)，m = target 長度，n = words[0] 長度 - 空間複雜度:
O(m * n)
class Solution {
fun numWays(words: Array<String>, target: String): Int {
val MOD = 1_000_000_007L
val n = words[0].length
val m = target.length
val freq = Array(n) { IntArray(26) }
for (word in words) {
for (j in word.indices) {
freq[j][word[j] - 'a']++
}
}
val dp = Array(m + 1) { LongArray(n + 1) }
for (j in 0..n) dp[0][j] = 1
for (i in 1..m) {
for (j in 1..n) {
dp[i][j] = dp[i][j - 1] // 跳過位置 j
dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * freq[j - 1][target[i - 1] - 'a']) % MOD
}
}
return dp[m][n].toInt()
}
}⭐2: 1D DP（空間優化）#
- 概念: 壓縮掉位置維度，逆序更新 target 維度。
- 時間複雜度:
O(m * n) - 空間複雜度:
O(m)
class Solution {
fun numWays(words: Array<String>, target: String): Int {
val MOD = 1_000_000_007L
val n = words[0].length
val m = target.length
val freq = Array(n) { IntArray(26) }
for (word in words) {
for (j in word.indices) {
freq[j][word[j] - 'a']++
}
}
val dp = LongArray(m + 1)
dp[0] = 1
for (j in 0 until n) {
for (i in minOf(m, j + 1) downTo 1) {
dp[i] = (dp[i] + dp[i - 1] * freq[j][target[i - 1] - 'a']) % MOD
}
}
return dp[m].toInt()
}
}🔑 Takeaways#
- Pattern: 匹配型 DP — 類似子序列匹配，加上頻率計數
- 關鍵技巧: 預處理字元頻率矩陣將問題簡化；逆序更新避免重複使用同一位置