【Leetcode 每日一题】3291. 形成目标字符串需要的最少字符串数 I

问题背景

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

数据约束

$\le words.length \le 100$
$\le words[i].length \le 5 \times 10 ^ 3$
$\le 10 ^ 5$
$w or d s [i]$ 只包含小写英文字母
$\le target.length \le 5 \times 10 ^ 3$
$t a r g e t$ 只包含小写英文字母

解题过程

周赛第三题的水准，数据范围允许暴力解，似乎可以用前缀树搭配嵌套循环解决。遗憾的是我目前只会写前缀树，还不会用前缀树来解决问题。
既然要学，那就学习一下一般情形化的做法。这题可以看作将目标分割成几个部分，每个部分都是给定的数组中字符串的前缀。
要求选用的字符串尽可能少，就要每次覆盖的范围尽可能大，这就可以参考跳跃游戏 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;
    }
}