Skip to content

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]}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  int numWays(vector<string>& words, string target) {
    const int wordLength = words[0].length();
    vector<vector<int>> mem(target.length(), vector<int>(wordLength, -1));
    // counts[j] := the count map of words[i][j], where 0 <= i < |words|
    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, mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Returns the number of ways to form target[i..n) using word[j..n).
  int numWays(const string& target, int i, int j,
              const vector<vector<int>>& counts, vector<vector<int>>& mem) {
    if (i == target.length())
      return 1;
    if (j == counts.size())
      return 0;
    if (mem[i][j] != -1)
      return mem[i][j];
    return mem[i][j] = (numWays(target, i + 1, j + 1, counts, mem) *
                            static_cast<long>(counts[j][target[i] - 'a']) +
                        numWays(target, i, j + 1, counts, mem)) %
                       kMod;
  };
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public int numWays(String[] words, String target) {
    final int wordLength = words[0].length();
    Integer[][] mem = new Integer[target.length()][wordLength];
    // counts[j] := the count map of words[i][j], where 0 <= i < |words|
    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, mem);
  }

  private static final int kMod = 1_000_000_007;

  // Returns the number of ways to form target[i..n) using word[j..n).
  private int numWays(final String target, int i, int j, int[][] counts, Integer[][] mem) {
    if (i == target.length())
      return 1;
    if (j == counts.length)
      return 0;
    if (mem[i][j] != null)
      return mem[i][j];
    return mem[i][j] = (int) ((numWays(target, i + 1, j + 1, counts, mem) *
                                   (long) (counts[j][target.charAt(i) - 'a']) +
                               numWays(target, i, j + 1, counts, mem)) %
                              kMod);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def numWays(self, words: List[str], target: str) -> int:
    kMod = 1_000_000_007
    wordLength = len(words[0])
    # counts[j] := the count map of words[i][j], where 0 <= i < |words|
    counts = [collections.Counter() for _ in range(wordLength)]

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

    @functools.lru_cache(None)
    def dp(i: int, j: int):
      """Returns the number of ways to form target[i..n) using word[j..n)."""
      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]}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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] := the number of ways to form the first i characters of the
    // `target` using the j first characters in each word
    vector<vector<int>> dp(target.length() + 1, vector<int>(wordLength + 1));
    // counts[j] := the count map of words[i][j], where 0 <= i < |words|
    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 the word[j].
        dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % kMod;
      }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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] := the number of ways to form the first i characters of the
    // `target` using the j first characters in each word
    int[][] dp = new int[target.length() + 1][wordLength + 1];
    // counts[j] := the count map of words[i][j], where 0 <= i < |words|
    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 the word[j].
        dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % kMod;
      }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def numWays(self, words: List[str], target: str) -> int:
    kMod = 1_000_000_007
    wordLength = len(words[0])
    # dp[i][j] := the number of ways to form the first i characters of the
    # `target` using the j first characters in each word
    dp = [[0] * (wordLength + 1) for _ in range(len(target) + 1)]
    # counts[j] := the count map of words[i][j], where 0 <= i < |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 the 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})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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] := the number of ways to form the first i characters of the
    // `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()];
  };
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int numWays(String[] words, String target) {
    final int kMod = 1_000_000_007;
    final int wordLength = words[0].length();
    // dp[i] := the number of ways to form the 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()];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def numWays(self, words: List[str], target: str) -> int:
    kMod = 1_000_000_007
    # dp[i] := the number of ways to form the 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)]