Number of Ways to Form a Target String Given a Dictionary

Share

Count ways to form target by picking one character per index from words, left to right.

Example 1
Input: words=["acca","bbbb","caca"], target="aba" → Output: 6
Example 2
Input: words=["abba","baab"], target="bab" → Output: 4

Solution Approach

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
Java
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)