Question

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

中文文档

Description

You are given a list of strings of the same length words and a string target.

Your task is to form target using the given words under the following rules:

• target should be formed from left to right.
• To form the ith character (0-indexed) of target, you can choose the kth character of the jth string in words if target[i] = words[j][k].
• Once you use the kth character of the jth string of words, you can no longer use the xth character of any string in words where x <= k. In other words, all characters to the left of or at index k become unusuable for every string.
• Repeat the process until you form the string target.

Notice that you can use multiple characters from the same string in words provided the conditions above are met.

Return _the number of ways to form target from words_. Since the answer may be too large, return it modulo 109 + 7.

 

Example 1:

Input: words = ["acca","bbbb","caca"], target = "aba"
Output: 6
Explanation: There are 6 ways to form target.
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")

Example 2:

Input: words = ["abba","baab"], target = "bab"
Output: 4
Explanation: There are 4 ways to form target.
"bab" -> index 0 ("baab"), index 1 ("baab"), index 2 ("abba")
"bab" -> index 0 ("baab"), index 1 ("baab"), index 3 ("baab")
"bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab")
"bab" -> index 1 ("abba"), index 2 ("baab"), index 3 ("baab")

 

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• All strings in words have the same length.
• 1 <= target.length <= 1000
• words[i] and target contain only lowercase English letters.

Solutions

Solution 1: Preprocessing + Memory Search

We noticed that the length of each string in the string array $words$ is the same, so let's remember $n$, then we can preprocess a two-dimensional array $cnt$, where $cnt[j][c]$ represents the string array $words$ The number of characters $c$ in the $j$-th position of.

Next, we design a function $dfs(i, j)$, which represents the number of schemes that construct $target[i,..]$ and the currently selected character position from $words$ is $j$. Then the answer is $dfs(0, 0)$.

The calculation logic of function $dfs(i, j)$ is as follows:

• If $i \geq m$, it means that all characters in $target$ have been selected, then the number of schemes is $1$.
• If $j \geq n$, it means that all characters in $words$ have been selected, then the number of schemes is $0$.
• Otherwise, we can choose not to select the character in the $j$-th position of $words$, then the number of schemes is $dfs(i, j + 1)$; or we choose the character in the $j$-th position of $words$, then the number of schemes is $dfs(i + 1, j + 1) \times cnt[j][target[i] - 'a']$.

Finally, we return $dfs(0, 0)$. Note that the answer is taken in modulo operation.

The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Where $m$ is the length of the string $target$, and $n$ is the length of each string in the string array $words$.

class Solution:
  def numWays(self, words: List[str], target: str) -> int:
    @cache
    def dfs(i: int, j: int) -> int:
      if i >= m:
        return 1
      if j >= n:
        return 0
      ans = dfs(i + 1, j + 1) * cnt[j][ord(target[i]) - ord('a')]
      ans = (ans + dfs(i, j + 1)) % mod
      return ans

    m, n = len(target), len(words[0])
    cnt = [[0] * 26 for _ in range(n)]
    for w in words:
      for j, c in enumerate(w):
        cnt[j][ord(c) - ord('a')] += 1
    mod = 10**9 + 7
    return dfs(0, 0)

class Solution {
  private int m;
  private int n;
  private String target;
  private Integer[][] f;
  private int[][] cnt;
  private final int mod = (int) 1e9 + 7;

  public int numWays(String[] words, String target) {
    m = target.length();
    n = words[0].length();
    f = new Integer[m][n];
    this.target = target;
    cnt = new int[n][26];
    for (var w : words) {
      for (int j = 0; j < n; ++j) {
        cnt[j][w.charAt(j) - 'a']++;
      }
    }
    return dfs(0, 0);
  }

  private int dfs(int i, int j) {
    if (i >= m) {
      return 1;
    }
    if (j >= n) {
      return 0;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    long ans = dfs(i, j + 1);
    ans += 1L * dfs(i + 1, j + 1) * cnt[j][target.charAt(i) - 'a'];
    ans %= mod;
    return f[i][j] = (int) ans;
  }
}

class Solution {
public:
  int numWays(vector<string>& words, string target) {
    const int mod = 1e9 + 7;
    int m = target.size(), n = words[0].size();
    vector<vector<int>> cnt(n, vector<int>(26));
    for (auto& w : words) {
      for (int j = 0; j < n; ++j) {
        ++cnt[j][w[j] - 'a'];
      }
    }
    int f[m][n];
    memset(f, -1, sizeof(f));
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      if (i >= m) {
        return 1;
      }
      if (j >= n) {
        return 0;
      }
      if (f[i][j] != -1) {
        return f[i][j];
      }
      int ans = dfs(i, j + 1);
      ans = (ans + 1LL * dfs(i + 1, j + 1) * cnt[j][target[i] - 'a']) % mod;
      return f[i][j] = ans;
    };
    return dfs(0, 0);
  }
};

func numWays(words []string, target string) int {
  m, n := len(target), len(words[0])
  f := make([][]int, m)
  cnt := make([][26]int, n)
  for _, w := range words {
    for j, c := range w {
      cnt[j][c-'a']++
    }
  }
  for i := range f {
    f[i] = make([]int, n)
    for j := range f[i] {
      f[i][j] = -1
    }
  }
  const mod = 1e9 + 7
  var dfs func(i, j int) int
  dfs = func(i, j int) int {
    if i >= m {
      return 1
    }
    if j >= n {
      return 0
    }
    if f[i][j] != -1 {
      return f[i][j]
    }
    ans := dfs(i, j+1)
    ans = (ans + dfs(i+1, j+1)*cnt[j][target[i]-'a']) % mod
    f[i][j] = ans
    return ans
  }
  return dfs(0, 0)
}

function numWays(words: string[], target: string): number {
  const m = target.length;
  const n = words[0].length;
  const f = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
  const mod = 1e9 + 7;
  for (let j = 0; j <= n; ++j) {
    f[0][j] = 1;
  }
  const cnt = new Array(n).fill(0).map(() => new Array(26).fill(0));
  for (const w of words) {
    for (let j = 0; j < n; ++j) {
      ++cnt[j][w.charCodeAt(j) - 97];
    }
  }
  for (let i = 1; i <= m; ++i) {
    for (let j = 1; j <= n; ++j) {
      f[i][j] = f[i][j - 1] + f[i - 1][j - 1] * cnt[j - 1][target.charCodeAt(i - 1) - 97];
      f[i][j] %= mod;
    }
  }
  return f[m][n];
}

Solution 2: Preprocessing + Dynamic Programming

Similar to Solution 1, we can first preprocess a two-dimensional array $cnt$, where $cnt[j][c]$ represents the number of characters $c$ in the $j$-th position of the string array $words$.

Next, we define $f[i][j]$ which represents the number of ways to construct the first $i$ characters of $target$, and currently select characters from the first $j$ characters of each word in $words$. Then the answer is $f[m][n]$. Initially $f[0][j] = 1$, where $0 \leq j \leq n$.

Consider $f[i][j]$, where $i \gt 0$, $j \gt 0$. We can choose not to select the character in the $j$-th position of $words$, in which case the number of ways is $f[i][j - 1]$; or we choose the character in the $j$-th position of $words$, in which case the number of ways is $f[i - 1][j - 1] \times cnt[j - 1][target[i - 1] - 'a']$. Finally, we add the number of ways in these two cases, which is the value of $f[i][j]$.

Finally, we return $f[m][n]$. Note the mod operation of the answer.

The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Where $m$ is the length of the string $target$, and $n$ is the length of each string in the string array $words$.

class Solution:
  def numWays(self, words: List[str], target: str) -> int:
    m, n = len(target), len(words[0])
    cnt = [[0] * 26 for _ in range(n)]
    for w in words:
      for j, c in enumerate(w):
        cnt[j][ord(c) - ord('a')] += 1
    mod = 10**9 + 7
    f = [[0] * (n + 1) for _ in range(m + 1)]
    f[0] = [1] * (n + 1)
    for i in range(1, m + 1):
      for j in range(1, n + 1):
        f[i][j] = (
          f[i][j - 1]
          + f[i - 1][j - 1] * cnt[j - 1][ord(target[i - 1]) - ord('a')]
        )
        f[i][j] %= mod
    return f[m][n]

class Solution {
  public int numWays(String[] words, String target) {
    int m = target.length();
    int n = words[0].length();
    final int mod = (int) 1e9 + 7;
    long[][] f = new long[m + 1][n + 1];
    Arrays.fill(f[0], 1);
    int[][] cnt = new int[n][26];
    for (var w : words) {
      for (int j = 0; j < n; ++j) {
        cnt[j][w.charAt(j) - 'a']++;
      }
    }
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        f[i][j] = f[i][j - 1] + f[i - 1][j - 1] * cnt[j - 1][target.charAt(i - 1) - 'a'];
        f[i][j] %= mod;
      }
    }
    return (int) f[m][n];
  }
}

class Solution {
public:
  int numWays(vector<string>& words, string target) {
    int m = target.size(), n = words[0].size();
    const int mod = 1e9 + 7;
    long long f[m + 1][n + 1];
    memset(f, 0, sizeof(f));
    fill(f[0], f[0] + n + 1, 1);
    vector<vector<int>> cnt(n, vector<int>(26));
    for (auto& w : words) {
      for (int j = 0; j < n; ++j) {
        ++cnt[j][w[j] - 'a'];
      }
    }
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        f[i][j] = f[i][j - 1] + f[i - 1][j - 1] * cnt[j - 1][target[i - 1] - 'a'];
        f[i][j] %= mod;
      }
    }
    return f[m][n];
  }
};

func numWays(words []string, target string) int {
  const mod = 1e9 + 7
  m, n := len(target), len(words[0])
  f := make([][]int, m+1)
  for i := range f {
    f[i] = make([]int, n+1)
  }
  for j := range f[0] {
    f[0][j] = 1
  }
  cnt := make([][26]int, n)
  for _, w := range words {
    for j, c := range w {
      cnt[j][c-'a']++
    }
  }
  for i := 1; i <= m; i++ {
    for j := 1; j <= n; j++ {
      f[i][j] = f[i][j-1] + f[i-1][j-1]*cnt[j-1][target[i-1]-'a']
      f[i][j] %= mod
    }
  }
  return f[m][n]
}