Welcome to Subscribe On Youtube
3291. Minimum Number of Valid Strings to Form Target I
Description
You are given an array of strings words and a string target.
A string x is called valid if x is a prefix of any string in words.
Return the minimum number of valid strings that can be concatenated to form target. If it is not possible to form target, return -1.
Example 1:
Input: words = ["abc","aaaaa","bcdef"], target = "aabcdabc"
Output: 3
Explanation:
The target string can be formed by concatenating:
- Prefix of length 2 of
words[1], i.e."aa". - Prefix of length 3 of
words[2], i.e."bcd". - Prefix of length 3 of
words[0], i.e."abc".
Example 2:
Input: words = ["abababab","ab"], target = "ababaababa"
Output: 2
Explanation:
The target string can be formed by concatenating:
- Prefix of length 5 of
words[0], i.e."ababa". - Prefix of length 5 of
words[0], i.e."ababa".
Example 3:
Input: words = ["abcdef"], target = "xyz"
Output: -1
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 5 * 103- The input is generated such that
sum(words[i].length) <= 105. words[i]consists only of lowercase English letters.1 <= target.length <= 5 * 103targetconsists only of lowercase English letters.
Solutions
Solution 1: Trie + Memoization
We can use a trie to store all valid strings and then use memoization to calculate the answer.
We design a function $\textit{dfs}(i)$, which represents the minimum number of strings needed to concatenate starting from the $i$-th character of the string $\textit{target}$. The answer is $\textit{dfs}(0)$.
The function $\textit{dfs}(i)$ is calculated as follows:
- If $i \geq n$, it means the string $\textit{target}$ has been completely traversed, so we return $0$;
- Otherwise, we can find valid strings in the trie that start with $\textit{target}[i]$, and then recursively calculate $\textit{dfs}(i + \text{len}(w))$, where $w$ is the valid string found. We take the minimum of these values and add $1$ as the return value of $\textit{dfs}(i)$.
To avoid redundant calculations, we use memoization.
The time complexity is $O(n^2 + L)$, and the space complexity is $O(n + L)$. Here, $n$ is the length of the string $\textit{target}$, and $L$ is the total length of all valid strings.
-
class Trie { Trie[] children = new Trie[26]; void insert(String w) { Trie node = this; for (int i = 0; i < w.length(); ++i) { int j = w.charAt(i) - 'a'; if (node.children[j] == null) { node.children[j] = new Trie(); } node = node.children[j]; } } } class Solution { private Integer[] f; private char[] s; private Trie trie; private final int inf = 1 << 30; public int minValidStrings(String[] words, String target) { trie = new Trie(); for (String w : words) { trie.insert(w); } s = target.toCharArray(); f = new Integer[s.length]; int ans = dfs(0); return ans < inf ? ans : -1; } private int dfs(int i) { if (i >= s.length) { return 0; } if (f[i] != null) { return f[i]; } Trie node = trie; f[i] = inf; for (int j = i; j < s.length; ++j) { int k = s[j] - 'a'; if (node.children[k] == null) { break; } f[i] = Math.min(f[i], 1 + dfs(j + 1)); node = node.children[k]; } return f[i]; } } -
class Trie { public: Trie* children[26]{}; void insert(string& word) { Trie* node = this; for (char& c : word) { int i = c - 'a'; if (!node->children[i]) { node->children[i] = new Trie(); } node = node->children[i]; } } }; class Solution { public: int minValidStrings(vector<string>& words, string target) { int n = target.size(); Trie* trie = new Trie(); for (auto& w : words) { trie->insert(w); } const int inf = 1 << 30; int f[n]; memset(f, -1, sizeof(f)); auto dfs = [&](auto&& dfs, int i) -> int { if (i >= n) { return 0; } if (f[i] != -1) { return f[i]; } f[i] = inf; Trie* node = trie; for (int j = i; j < n; ++j) { int k = target[j] - 'a'; if (!node->children[k]) { break; } node = node->children[k]; f[i] = min(f[i], 1 + dfs(dfs, j + 1)); } return f[i]; }; int ans = dfs(dfs, 0); return ans < inf ? ans : -1; } }; -
def min(a: int, b: int) -> int: return a if a < b else b class Trie: def __init__(self): self.children: List[Optional[Trie]] = [None] * 26 def insert(self, w: str): node = self for i in map(lambda c: ord(c) - 97, w): if node.children[i] is None: node.children[i] = Trie() node = node.children[i] class Solution: def minValidStrings(self, words: List[str], target: str) -> int: @cache def dfs(i: int) -> int: if i >= n: return 0 node = trie ans = inf for j in range(i, n): k = ord(target[j]) - 97 if node.children[k] is None: break node = node.children[k] ans = min(ans, 1 + dfs(j + 1)) return ans trie = Trie() for w in words: trie.insert(w) n = len(target) ans = dfs(0) return ans if ans < inf else -1 -
type Trie struct { children [26]*Trie } func (t *Trie) insert(word string) { node := t for _, c := range word { idx := c - 'a' if node.children[idx] == nil { node.children[idx] = &Trie{} } node = node.children[idx] } } func minValidStrings(words []string, target string) int { n := len(target) trie := &Trie{} for _, w := range words { trie.insert(w) } const inf int = 1 << 30 f := make([]int, n) var dfs func(int) int dfs = func(i int) int { if i >= n { return 0 } if f[i] != 0 { return f[i] } node := trie f[i] = inf for j := i; j < n; j++ { k := int(target[j] - 'a') if node.children[k] == nil { break } f[i] = min(f[i], 1+dfs(j+1)) node = node.children[k] } return f[i] } if ans := dfs(0); ans < inf { return ans } return -1 } -
class Trie { children: (Trie | null)[] = Array(26).fill(null); insert(word: string): void { let node: Trie = this; for (const c of word) { const i = c.charCodeAt(0) - 'a'.charCodeAt(0); if (!node.children[i]) { node.children[i] = new Trie(); } node = node.children[i]; } } } function minValidStrings(words: string[], target: string): number { const n = target.length; const trie = new Trie(); for (const w of words) { trie.insert(w); } const inf = 1 << 30; const f = Array(n).fill(0); const dfs = (i: number): number => { if (i >= n) { return 0; } if (f[i]) { return f[i]; } f[i] = inf; let node: Trie | null = trie; for (let j = i; j < n; ++j) { const k = target[j].charCodeAt(0) - 'a'.charCodeAt(0); if (!node?.children[k]) { break; } node = node.children[k]; f[i] = Math.min(f[i], 1 + dfs(j + 1)); } return f[i]; }; const ans = dfs(0); return ans < inf ? ans : -1; }