Count ways to form target by picking one character per index from words, left to right.
Input: words=["acca","bbbb","caca"], target="aba" → Output: 6
Input: words=["abba","baab"], target="bab" → Output: 4
DP: dp[j] = ways to form target[0..j-1]. For each column, update dp using character counts.
- Count frequency of each char at each column position
- dp[j] = ways to form first j chars of target
- For each column (left to right): update dp[j] += dp[j-1] * count[col][target[j-1]]
- Process in reverse to avoid using same column twice
- Return dp[m] mod 1e9+7
public int numWays(String[] words, String target) {
int n = words[0].length(), m = target.length();
long MOD = 1_000_000_007L;
int[][] cnt = new int[n][26];
for (String w : words) for (int i = 0; i < n; i++) cnt[i][w.charAt(i)-'a']++;
long[] dp = new long[m + 1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
int c = cnt[i][target.charAt(Math.min(i,m-1))-'a'];
for (int j = Math.min(i+1, m); j >= 1; j--)
dp[j] = (dp[j] + dp[j-1] * cnt[i][target.charAt(j-1)-'a']) % MOD;
}
return (int) dp[m];
}
- Time Complexity: O(n*m)
- Space Complexity: O(m)