给你一个字符串数组 words 和一个字符串 target。
如果字符串 x 是 words 中 任意 字符串的
前缀
，则认为 x 是一个 有效 字符串。
现计划通过 连接 有效字符串形成 target ，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 target，则返回 -1。
示例 1：
输入： words = [“abc”,”aaaaa”,”bcdef”], target = “aabcdabc”
输出： 3
解释：
target 字符串可以通过连接以下有效字符串形成：
words[1] 的长度为 2 的前缀，即 “aa”。
words[2] 的长度为 3 的前缀，即 “bcd”。
words[0] 的长度为 3 的前缀，即 “abc”。
示例 2：
输入： words = [“abababab”,”ab”], target = “ababaababa”
输出： 2
解释：
target 字符串可以通过连接以下有效字符串形成：
words[0] 的长度为 5 的前缀，即 “ababa”。
words[0] 的长度为 5 的前缀，即 “ababa”。
示例 3：
输入： words = [“abcdef”], target = “xyz”
输出： -1
提示：
1 <= words.length <= 100
1 <= words[i].length <= 5 * 103
输入确保 sum(words[i].length) <= 105。
words[i] 只包含小写英文字母。
1 <= target.length <= 5 * 103
target 只包含小写英文字母。
//解法 二分+dp 需要先做45. 跳跃游戏 II理解可跳
(45是一道区间贪心，要在满足最大延伸范围内寻找下一跳，让下一跳尽可能远)
(on 的做法是维护两个变量cur next 表示当前最大延伸位置 和路途中遇到的最大的下一跳的位置 一旦i等于cur 就把cur=next 并且ans++
如果不保证一定到达终点 那么在i==cur的时候 发现next没有更新还是cur 相当于原地踏步
)
剩下的就是计算maxjump数组
字符串哈希优化
设dp[i]为以target字符数组i下标结尾的最小操作次数，则dp[i] = dp[j] + 1 （j为最早超过i的位置）
check函数用来搜索最大可跳的距离，这里没有用哈希字符串优化，实测中该数据的确发生了碰撞冲突，那些通过的实际上是绕开了这个较小的碰撞概率
如果d距离可跳，根据前缀性质，则d-1距离必然可跳，二分搜索问题为[True,True,True..... True,False,False…]问题，是一个单调函数，具有可行性
时间复杂度O(n2logn)
class Solution:
def minValidStrings(self, words: List[str], target: str) -> int:
n = len(target)
hash = [set() for _ in range(n + 1)]
for w in words:
for i in range(min(n, len(w))):
hash[i + 1].add(w[:i + 1])
j = -1
dp = [0 for _ in range(n + 1)]
for i in range(n):
while j < i and (
target[j + 1] not in hash[1]
or bisect_right(range(j + 1, n), False, key=lambda e: target[j + 1:e + 1] not in hash[e - j]) + j < i):
j += 1
if j >= i:
break
dp[i + 1] = dp[j + 1] + 1
return -1 if dp[-1] == 0 else dp[-1]
作者：angebowry
//
//字典树+记忆化搜索
待我再研究研究
import java.util.*;
class TrieNode {
Map<Character, TrieNode> children;
boolean isEnd;
public TrieNode() {
children = new HashMap<>();
isEnd = false;
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node.children.putIfAbsent(c, new TrieNode());
node = node.children.get(c);
}
node.isEnd = true;
}
public TrieNode searchPrefix(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
if (!node.children.containsKey(c)) {
return null;
}
node = node.children.get(c);
}
return node;
}
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
}
class Solution {
private Trie trie;
private String target;
private Map<String, Integer> memo;
public int minValidStrings(String[] words, String target) {
this.trie = new Trie();
this.target = target;
this.memo = new HashMap<>();
for (String word : words) {
trie.insert(word);
}
return dfs(0, target.length() - 1);
}
private int dfs(int start, int end) {
String key = start + "-" + end;
if (memo.containsKey(key)) {
return memo.get(key);
}
if (trie.searchPrefix(target.substring(start, end + 1)) != null) {
memo.put(key, 1);
return 1;
}
int res = Integer.MAX_VALUE;
TrieNode node = trie.root;
for (int k = start; k <= end; k++) {
char c = target.charAt(k);
if (!node.children.containsKey(c)) {
memo.put(key, res == Integer.MAX_VALUE ? -1 : res);
return res == Integer.MAX_VALUE ? -1 : res;
}
int n1 = dfs(k + 1, end);
if (n1 != -1) {
res = Math.min(res, n1 + 1);
}
node = node.children.get(c);
}
memo.put(key, res == Integer.MAX_VALUE ? -1 : res);
return res == Integer.MAX_VALUE ? -1 : res;
}
}
//3292 II 字符串哈希+二分
预处理每个 words[i] 的每个前缀的字符串哈希值，按照前缀长度分组，保存到不同的集合中。每个集合保存的是相同前缀长度的哈希值。
由于 words 的长度至多为 100，所以每个集合至多保存 100 个哈希值，根据生日攻击理论，单模哈希绰绰有余，碰撞概率很小。
然后对于每个 i，二分求出 maxJumps[i]。
二分的 check(mid) 函数怎么写？判断从 target[i] 开始的长为 mid 的子串，哈希值是否在集合中。
作者：灵茶山艾府
class Solution {
private static final int MOD = 1_070_777_777;
public int minValidStrings(String[] words, String target) {
char[] t = target.toCharArray();
int n = t.length;
// 多项式字符串哈希（方便计算子串哈希值）
// 哈希函数 hash(s) = s[0] * base^(n-1) + s[1] * base^(n-2) + ... + s[n-2] * base + s[n-1]
final int BASE = (int) 8e8 + new Random().nextInt((int) 1e8); // 随机 base，防止 hack
int[] powBase = new int[n + 1]; // powBase[i] = base^i
int[] preHash = new int[n + 1]; // 前缀哈希值 preHash[i] = hash(target[0] 到 target[i-1])
powBase[0] = 1;
for (int i = 0; i < n; i++) {
powBase[i + 1] = (int) ((long) powBase[i] * BASE % MOD);
preHash[i + 1] = (int) (((long) preHash[i] * BASE + t[i]) % MOD); // 秦九韶算法计算多项式哈希
}
int maxLen = 0;
for (String w : words) {
maxLen = Math.max(maxLen, w.length());
}
Set<Integer>[] sets = new HashSet[maxLen];
Arrays.setAll(sets, i -> new HashSet<>());
for (String w : words) {
long h = 0;
for (int j = 0; j < w.length(); j++) {
h = (h * BASE + w.charAt(j)) % MOD;
sets[j].add((int) h); // 注意 j 从 0 开始
}
}
int ans = 0;
int curR = 0; // 已建造的桥的右端点
int nxtR = 0; // 下一座桥的右端点的最大值
for (int i = 0; i < n; i++) {
int maxJump = calcMaxJump(i, preHash, powBase, sets);
nxtR = Math.max(nxtR, i + maxJump);
if (i == curR) { // 到达已建造的桥的右端点
if (i == nxtR) { // 无论怎么造桥，都无法从 i 到 i+1
return -1;
}
curR = nxtR; // 造一座桥
ans++;
}
}
return ans;
}
private int calcMaxJump(int i, int[] preHash, int[] powBase, Set<Integer>[] sets) {
// 开区间二分，left 一定满足要求，right 一定不满足要求
int left = 0;
int right = Math.min(preHash.length - 1 - i, sets.length) + 1;
while (left + 1 < right) {
int mid = (left + right) >>> 1;
long subHash = (((long) preHash[i + mid] - (long) preHash[i] * powBase[mid]) % MOD + MOD) % MOD;
if (sets[mid - 1].contains((int) subHash)) {
left = mid;
} else {
right = mid;
}
}
return left;
}
}
