网站后台有安全狗,新平台推广,门户网站建设的建议,做网站多问题背景
给你一个字符串数组 w o r d s words words 和一个字符串 t a r g e t target target。 如果字符串 x x x 是 w o r d s words words 中 任意 字符串的 前缀#xff08;字符串的前缀是从字符串的开头开始并延伸到其中任意点的子串#xff09;#xff0c;则认为…问题背景
给你一个字符串数组 w o r d s words words 和一个字符串 t a r g e t target target。 如果字符串 x x x 是 w o r d s words words 中 任意 字符串的 前缀字符串的前缀是从字符串的开头开始并延伸到其中任意点的子串则认为 x x x 是一个 有效 字符串。 现计划通过 连接 有效字符串形成 t a r g e t target target请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 t a r g e t target target则返回 − 1 -1 −1。
数据约束 1 ≤ w o r d s . l e n g t h ≤ 100 1 \le words.length \le 100 1≤words.length≤100 1 ≤ w o r d s [ i ] . l e n g t h ≤ 5 × 1 0 3 1 \le words[i].length \le 5 \times 10 ^ 3 1≤words[i].length≤5×103 s u m ( w o r d s [ i ] . l e n g t h ) ≤ 1 0 5 sum(words[i].length) \le 10 ^ 5 sum(words[i].length)≤105 w o r d s [ i ] words[i] words[i] 只包含小写英文字母 1 ≤ t a r g e t . l e n g t h ≤ 5 × 1 0 3 1 \le target.length \le 5 \times 10 ^ 3 1≤target.length≤5×103 t a r g e t target target 只包含小写英文字母
解题过程
周赛第三题的水准数据范围允许暴力解似乎可以用前缀树搭配嵌套循环解决。遗憾的是我目前只会写前缀树还不会用前缀树来解决问题。 既然要学那就学习一下一般情形化的做法。这题可以看作将目标分割成几个部分每个部分都是给定的数组中字符串的前缀。 要求选用的字符串尽可能少就要每次覆盖的范围尽可能大这就可以参考 跳跃游戏 II 和 灌溉花园的最少水龙头数目。没有保证一定能实现目标要单独处理。
分割的部分需要用到 扩展 KMP 算法也叫字符串的 Z 函数它的作用是求出一个字符串中各个后缀与它本身的最长公共前缀的长度。这个东西今天是第一次见不要求马上能学会先见识一下。 还有使用字符串哈希和 AC 自动机的做法因为相应的算法还没有掌握先不作要求可以暂时把重点放在吃透造桥问题的贪心做法上。
具体实现
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;}
}
