Welcome to Subscribe On Youtube

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$.

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$.

Solution 3: Preprocessing + Dynamic Programming

Thinking

Words share one length, and letters in the same column are interchangeable. Backtracking over the words repeats work once $m$ and $n$ reach $1000$.

Count letter $c$ in column $j$ as $\textit{cnt}[j][c]$. Building $\textit{target}[i:]$ either skips column $j$ or uses it for the current character and multiplies by that count.

Both choices read a later column. Walking from column $0$ to column $n$ is a chain of length $n$. Python raises RecursionError when $n=1000$.

Fill a table instead. $f[i][j]$ is still the number of ways to build $\textit{target}[i:]$ from column $j$ onward. A finished target is $1$ and running out of columns is $0$, so set $f[m][j]=1$ first. Decreasing $i$ and $j$ leaves $f[i][j+1]$ and $f[i+1][j+1]$ already known.

Each string in $words$ has the same length $n$, so preprocess $cnt$, where $cnt[j][c]$ is the number of times character $c$ appears in column $j$.

Let $f[i][j]$ be the number of ways to build $target[i,..]$ starting from column $j$. The answer is $f[0][0]$.

When $i = m$, every character of $target$ has been chosen, so the value is $1$. When $j = n$ and $i < m$, the columns are exhausted before the target is finished, so the value is $0$. Set $f[m][j] = 1$ for $0 \leq j \leq n$, and leave every other cell at $0$.

For the remaining states, let $i$ run from $m - 1$ down to $0$ and $j$ from $n - 1$ down to $0$. Skipping column $j$ contributes $f[i][j + 1]$. Taking it contributes $f[i + 1][j + 1] \times cnt[j][target[i] - ‘a’]$. Add the two contributions and reduce modulo $10^9 + 7$ to obtain $f[i][j]$.

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

• Java
• C++
• Python
• Go
• TypeScript

• 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;
      }
  }
  
  
  // Solution 2
  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];
      }
  }
  
  
  
  // Solution 3
  class Solution {
      public int numWays(String[] words, String target) {
          int m = target.length();
          int n = words[0].length();
          final int mod = (int) 1e9 + 7;
          int[][] cnt = new int[n][26];
          for (var w : words) {
              for (int j = 0; j < n; ++j) {
                  cnt[j][w.charAt(j) - 'a']++;
              }
          }
          int[][] f = new int[m + 1][n + 1];
          for (int j = 0; j <= n; ++j) {
              f[m][j] = 1;
          }
          for (int i = m - 1; i >= 0; --i) {
              for (int j = n - 1; j >= 0; --j) {
                  long ans = f[i][j + 1];
                  ans += 1L * f[i + 1][j + 1] * cnt[j][target.charAt(i) - 'a'];
                  f[i][j] = (int) (ans % mod);
              }
          }
          return f[0][0];
      }
  }
  
  

• 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);
      }
  };
  
  
  // Solution 2
  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];
      }
  };
  
  
  
  // Solution 3
  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'];
              }
          }
          vector<vector<int>> f(m + 1, vector<int>(n + 1));
          for (int j = 0; j <= n; ++j) {
              f[m][j] = 1;
          }
          for (int i = m - 1; i >= 0; --i) {
              for (int j = n - 1; j >= 0; --j) {
                  long long ans = f[i][j + 1];
                  ans += 1LL * f[i + 1][j + 1] * cnt[j][target[i] - 'a'];
                  f[i][j] = ans % mod;
              }
          }
          return f[0][0];
      }
  };
  
  

• 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)
  
  
  # Solution 2
  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]
  
  
  
  # Solution 3
  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)]
          for j in range(n + 1):
              f[m][j] = 1
          for i in range(m - 1, -1, -1):
              for j in range(n - 1, -1, -1):
                  ans = f[i + 1][j + 1] * cnt[j][ord(target[i]) - ord('a')]
                  f[i][j] = (ans + f[i][j + 1]) % mod
          return f[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)
  }
  
  
  // Solution 2
  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]
  }
  
  
  
  // Solution 3
  func numWays(words []string, target string) int {
  	m, n := len(target), len(words[0])
  	cnt := make([][26]int, n)
  	for _, w := range words {
  		for j, c := range w {
  			cnt[j][c-'a']++
  		}
  	}
  	const mod = 1e9 + 7
  	f := make([][]int, m+1)
  	for i := range f {
  		f[i] = make([]int, n+1)
  	}
  	for j := range f[m] {
  		f[m][j] = 1
  	}
  	for i := m - 1; i >= 0; i-- {
  		for j := n - 1; j >= 0; j-- {
  			ans := f[i][j+1] + f[i+1][j+1]*cnt[j][target[i]-'a']
  			f[i][j] = ans % mod
  		}
  	}
  	return f[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 3
  function numWays(words: string[], target: string): number {
      const m = target.length;
      const n = words[0].length;
      const mod = 1e9 + 7;
      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];
          }
      }
      const f = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
      for (let j = 0; j <= n; ++j) {
          f[m][j] = 1;
      }
      for (let i = m - 1; i >= 0; --i) {
          for (let j = n - 1; j >= 0; --j) {
              const ans = f[i][j + 1] + f[i + 1][j + 1] * cnt[j][target.charCodeAt(i) - 97];
              f[i][j] = ans % mod;
          }
      }
      return f[0][0];
  }
  
  

All Problems

All Solutions