什么是跨境电商主要做什么_网络营销管理名词解释_东莞谷歌推广公司_百度首页排名优化价格

问题背景

给你一个字符串数组 $words$ 和一个字符串 $target$。
如果字符串 $x$ 是 $words$ 中 任意 字符串的 前缀（字符串的前缀是从字符串的开头开始并延伸到其中任意点的子串），则认为 $x$ 是一个 有效 字符串。
现计划通过 连接 有效字符串形成 $target$，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 $target$，则返回 $-1$。

数据约束

• $1\le words.length\le 100$
• $1\le words[i].length\le 5\times 10^4$
• $sum(words[i].length)\le 10^5$
• $words[i]$ 只包含小写英文字母
• $1\le target.length\le 5\times 10^4$
• $target$ 只包含小写英文字母

解题过程

周赛第四题，和第三题之间有数据范围上的区别。
一般的做法 昨天已经分析过了，不多赘述。

具体实现

class Solution {public int minValidStrings(String[] words, String target) {int n = target.length();int[] maxJumps = new int[n];for(String word : words) {// 把目标拼到这个单词的后面，就可以求出 Z 函数来辅助计算每个字符串可取的最大前缀了// 加一个特殊字符，防止下标越界int[] z = calcZ(word + "#" + target);int m = word.length() + 1; // 这里额外加的长度，是用来修正特殊字符的// 求出目标每个位置上能够匹配到的最大前缀长度for(int i = 0; i < n; i ++) {maxJumps[i] = Math.max(maxJumps[i], z[m + i]);}}return jump(maxJumps);}// Z 函数private int[] calcZ(String s) {char[] chS = s.toCharArray();int n = chS.length;int[] z = new int[n];int left = 0, right = 0;for(int i = 1; i < n; i++) {if(i <= right) {z[i] = Math.min(z[i - left], right - i + 1);}while(i + z[i] < n && chS[z[i]] == chS[i + z[i]]) {left = i;right = i + z[i];z[i]++;}}return z;}// 造桥问题的解，参见 Leetcode 45.跳跃游戏 II 和 Leetcode 1326.灌溉花园的最少水龙头数目private int jump(int[] maxJumps) {int res = 0;int curEnd = 0;int nextEnd = 0;for(int i = 0; i < maxJumps.length; i++) {nextEnd = Math.max(nextEnd, i + maxJumps[i]);if(i == curEnd) {if(i == nextEnd) {return -1;}curEnd = nextEnd;res++;}}return res;}
}