1639. Number of Ways to Form a Target String Given a Dictionary

Approach 1: Top-down

• Time: $O(\Sigma |\texttt{words[i]}| + \texttt{target} \cdot |\texttt{words[i]}|)$
• Space: $O(\texttt{target} \cdot |\texttt{words[i]}|)$

C++JavaPython

class Solution {
 public:
  int numWays(vector<string>& words, string target) {
    const int wordLength = words[0].length();
    // dp(i, j) := # of ways to form target[i:] using word[j:]
    dp.resize(target.length(), vector<int>(wordLength, -1));
    // counts[j] := count map for words[i][j] where 0 <= i < words.size()
    vector<vector<int>> counts(wordLength, vector<int>(26));

    for (int i = 0; i < wordLength; ++i)
      for (const string& word : words)
        ++counts[i][word[i] - 'a'];

    return numWays(target, 0, 0, counts);
  }

 private:
  static constexpr int kMod = 1'000'000'007;
  vector<vector<int>> dp;

  int numWays(const string& target, int i, int j,
              const vector<vector<int>>& counts) {
    if (i == target.length())
      return 1;
    if (j == counts.size())
      return 0;
    if (dp[i][j] != -1)
      return dp[i][j];
    return dp[i][j] = (numWays(target, i + 1, j + 1, counts) *
                           static_cast<long>(counts[j][target[i] - 'a']) +
                       numWays(target, i, j + 1, counts)) %
                      kMod;
  };
};

class Solution {
  public int numWays(String[] words, String target) {
    final int wordLength = words[0].length();
    dp = new Integer[target.length()][wordLength];
    int[][] counts = new int[wordLength][26];

    for (int i = 0; i < wordLength; ++i)
      for (final String word : words)
        ++counts[i][word.charAt(i) - 'a'];

    return numWays(target, 0, 0, counts);
  }

  private static final int kMod = 1_000_000_007;
  private Integer[][] dp;

  private int numWays(final String target, int i, int j, int[][] counts) {
    if (i == target.length())
      return 1;
    if (j == counts.length)
      return 0;
    if (dp[i][j] != null)
      return dp[i][j];
    return dp[i][j] = (int) ((numWays(target, i + 1, j + 1, counts) *
                                  (long) (counts[j][target.charAt(i) - 'a']) +
                              numWays(target, i, j + 1, counts)) %
                             kMod);
  }
}

class Solution:
  def numWays(self, words: List[str], target: str) -> int:
    kMod = 1_000_000_007
    wordLength = len(words[0])
    # dp[i][j] := # of ways to form first i characters of target using j first characters in each word
    dp = [[0] * (wordLength + 1) for _ in range(len(target) + 1)]
    # counts[j] := count map for words[i][j] where 0 <= i < len(words)
    counts = [collections.Counter() for _ in range(wordLength)]

    for i in range(wordLength):
      for word in words:
        counts[i][word[i]] += 1

    # dp(i, j) := # of ways to form target[i:] using word[j:]
    @functools.lru_cache(None)
    def dp(i: int, j: int):
      if i == len(target):
        return 1
      if j == wordLength:
        return 0
      return (dp(i + 1, j + 1) * counts[j][target[i]] + dp(i, j + 1)) % kMod

    return dp(0, 0)

Approach 2: Bottom-up 2D DP

• Time: $O(\Sigma |\texttt{words[i]}| + \texttt{target} \cdot |\texttt{words[i]}|)$
• Space: $O(\texttt{target} \cdot |\texttt{words[i]}|)$

C++JavaPython

class Solution {
 public:
  int numWays(vector<string>& words, string target) {
    constexpr int kMod = 1'000'000'007;
    const int wordLength = words[0].length();
    // dp[i][j] := # of ways to form first i characters of target using j first
    // characters in each word
    vector<vector<int>> dp(target.length() + 1, vector<int>(wordLength + 1));
    // counts[j] := count map for words[i][j] where 0 <= i < words.size()
    vector<vector<int>> counts(wordLength, vector<int>(26));

    for (int i = 0; i < wordLength; ++i)
      for (const string& word : words)
        ++counts[i][word[i] - 'a'];

    dp[0][0] = 1;

    for (int i = 0; i <= target.length(); ++i)
      for (int j = 0; j < wordLength; ++j) {
        if (i < target.length())
          // Pick the character target[i] from word[j].
          dp[i + 1][j + 1] =
              dp[i][j] * static_cast<long>(counts[j][target[i] - 'a']) % kMod;
        // Skip word[j].
        dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % kMod;
      }

    return dp[target.length()][wordLength];
  };
};

class Solution {
  public int numWays(String[] words, String target) {
    final int kMod = 1_000_000_007;
    final int wordLength = words[0].length();
    // dp[i][j] := # of ways to form first i characters of target using j first
    // characters in each word
    int[][] dp = new int[target.length() + 1][wordLength + 1];
    // counts[j] := count map for words[i][j] where 0 <= i < words.size()
    int[][] counts = new int[wordLength][26];

    for (int i = 0; i < wordLength; ++i)
      for (final String word : words)
        ++counts[i][word.charAt(i) - 'a'];

    dp[0][0] = 1;

    for (int i = 0; i <= target.length(); ++i)
      for (int j = 0; j < wordLength; ++j) {
        if (i < target.length())
          // Pick the character target[i] from word[j].
          dp[i + 1][j + 1] = (int) ((dp[i][j] * (long) counts[j][target.charAt(i) - 'a']) % kMod);
        // Skip word[j].
        dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % kMod;
      }

    return dp[target.length()][wordLength];
  }
}

class Solution:
  def numWays(self, words: List[str], target: str) -> int:
    kMod = 1_000_000_007
    wordLength = len(words[0])
    # dp[i][j] := # of ways to form first i characters of target using j first characters in each word
    dp = [[0] * (wordLength + 1) for _ in range(len(target) + 1)]
    # counts[j] := count map for words[i][j] where 0 <= i < len(words)
    counts = [collections.Counter() for _ in range(wordLength)]

    for i in range(wordLength):
      for word in words:
        counts[i][word[i]] += 1

    dp[0][0] = 1

    for i in range(len(target) + 1):
      for j in range(wordLength):
        if i < len(target):
          # Pick the character target[i] from word[j].
          dp[i + 1][j + 1] = dp[i][j] * counts[j][target[i]]
          dp[i + 1][j + 1] %= kMod
        # Skip word[j].
        dp[i][j + 1] += dp[i][j]
        dp[i][j + 1] %= kMod

    return dp[len(target)][wordLength]

Approach 3: Bottom-up 1D DP

• Time: $O(\Sigma |\texttt{words[i]}| + \texttt{target} \cdot |\texttt{words[i]}|)$
• Space: $O(\texttt{target})$

C++JavaPython

class Solution {
 public:
  int numWays(vector<string>& words, string target) {
    constexpr int kMod = 1'000'000'007;
    const int wordLength = words[0].length();
    // dp[i] := # of ways to form first i characters of target
    vector<long> dp(target.size() + 1);
    dp[0] = 1;

    for (int j = 0; j < wordLength; ++j) {
      vector<int> count(26);
      for (const string& word : words)
        ++count[word[j] - 'a'];
      for (int i = target.size(); i > 0; --i) {
        dp[i] += dp[i - 1] * count[target[i - 1] - 'a'];
        dp[i] %= kMod;
      }
    }

    return dp[target.length()];
  };
};

class Solution {
  public int numWays(String[] words, String target) {
    final int kMod = 1_000_000_007;
    final int wordLength = words[0].length();
    // dp[i] := # of ways to form first i characters of target
    long[] dp = new long[target.length() + 1];
    dp[0] = 1;

    for (int j = 0; j < wordLength; ++j) {
      int[] count = new int[26];
      for (final String word : words)
        ++count[word.charAt(j) - 'a'];
      for (int i = target.length(); i > 0; --i) {
        dp[i] += dp[i - 1] * count[target.charAt(i - 1) - 'a'];
        dp[i] %= kMod;
      }
    }

    return (int) dp[target.length()];
  }
}

class Solution:
  def numWays(self, words: List[str], target: str) -> int:
    kMod = 1_000_000_007
    # dp[i] := # of ways to form first i characters of target
    dp = [0] * (len(target) + 1)
    dp[0] = 1

    for j in range(len(words[0])):
      count = collections.Counter(word[j] for word in words)
      for i in range(len(target), 0, -1):
        dp[i] += dp[i - 1] * count[target[i - 1]]
        dp[i] %= kMod

    return dp[len(target)]