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.
Python3
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
Java
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];
}
}
C++
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 = [&](this 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(j + 1));
}
return f[i];
};
int ans = dfs(0);
return ans < inf ? ans : -1;
}
};
Go
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
}
TypeScript
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;
}