LeetCode-in-Java
3291. Minimum Number of Valid Strings to Form Target I
Medium
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.
A prefix of a string is a substring that starts from the beginning of the string and extends to any point within it.
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.
Solution
public class Solution {
public int minValidStrings(String[] words, String target) {
TrieNode root = new TrieNode();
for (String word : words) {
insert(root, word);
}
int n = target.length();
int[] dp = new int[n];
for (int i = n - 1; i >= 0; i--) {
dp[i] = Integer.MAX_VALUE;
TrieNode node = root;
for (int j = i; j < n; j++) {
int idx = target.charAt(j) - 'a';
if (node.children[idx] == null) {
break;
}
if (j == n - 1) {
dp[i] = 1;
} else if (dp[j + 1] >= 0) {
dp[i] = Math.min(dp[i], 1 + dp[j + 1]);
}
node = node.children[idx];
}
if (dp[i] == Integer.MAX_VALUE) {
dp[i] = -1;
}
}
return dp[0];
}
private void insert(TrieNode root, String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
}
private static class TrieNode {
TrieNode[] children = new TrieNode[26];
}
}