algorithm/problem/leetcode/3292

3292. 形成目标字符串需要的最少字符串数 II

给你一个字符串数组 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 * 10^4
• 输入确保 sum(words[i].length) <= 10^5.
• words[i] 只包含小写英文字母。
• 1 <= target.length <= 5 * 10^4
• target 只包含小写英文字母。

字符串哈希（按长度分组）+二分+贪心

这里贪心：跳跃游戏的贪心思想

class Solution {
    public int minValidStrings(String[] words, String target) {
        int n = target.length();
        // 多项式字符串哈希（方便计算子串哈希值）
        // 哈希函数 hash(s) = s[0] * base^(n-1) + s[1] * base^(n-2) + ... + s[n-2] * base + s[n-1]
        char[] t = target.toCharArray();
        final int MOD = 1_070_777_777;
        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 = Arrays.stream(words).mapToInt(word->word.length()).max().getAsInt();
        // 预处理每个 words[i] 的每个前缀的字符串哈希值，按照前缀长度分组
        Set<Integer> sets[] = new HashSet[maxLen+1];
        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+1].add((int) h);
            }
        }
        int res = 0, curR = 0, nxtR = 0;
        for (int i = 0; i < n; i++) {
            int l = i, r = Math.min(n, i+maxLen);
            while (l < r) {  // 二分获得当前位置i能匹配到的最长前缀（对应的target下标）
                int mid = l + (r-l+1)/2;
                int len = mid-i;
                long subHash = (((long) preHash[i + len] - (long) preHash[i] * powBase[len]) % MOD + MOD) % MOD;
                if (sets[len].contains((int)subHash)) l = mid;
                else r = mid-1;
            }
            nxtR = Math.max(nxtR, l);
            if (i == curR) {  // 到达已建造的桥的右端点
                if (i == nxtR) return -1;  // 无法到达
                curR = nxtR; // 造一座桥
                res++;
            }
        }
        return res;
    }
}