力扣12.17每日一题

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 * 104
  • 输入确保 sum(words[i].length) <= 105.
  • words[i] 只包含小写英文字母。
  • 1 <= target.length <= 5 * 104
  • target 只包含小写英文字母。

三种方法：Z 函数 / 字符串哈希 / AC 自动机（C++）

题意

把 target 划分成若干段，要求每一段都是某个 words[i] 的前缀。

返回最小划分成多少段。如果无法划分，返回 −1。

分析

示例 1 的 words=[abc,aaaaa,bcdef]，target=aabcdabc。

要让划分的段数尽量小，那么每一段的长度要尽量长？

虽然还不知道要怎么划分，但这启发我们考虑如下内容：

  • 从 target[0] 开始的段，最长可以是多长？答案是 2，因为 aa 是 words[1]=aaaaa 的前缀。
  • 从 target[1] 开始的段，最长可以是多长？答案是 3，因为 abc 是 words[0]=abc 的前缀。
  • 从 target[2] 开始的段，最长可以是多长？答案是 3，因为 bcd 是 words[2]=bcdef 的前缀。
  • ……

注意 words[i] 前缀的前缀还是 words[i] 的前缀。bcd 是 bcdef 的前缀，意味着 b 和 bc 也是 bcdef 的前缀。如果从 target[2] 开始的段，最长可以是 3，那么这个段的长度也可以是 1 或者 2。

如果我们算出了上面这些最长长度 2,3,3,⋯，那么问题就变成：

示例 1 的 maxJumps=[2,3,3,0,0,3,2,0]，跳法是 0→2→5→8。

现在剩下的问题是，如何计算 maxJumps 数组？

方法一：Z 函数

对于字符串 s，定义 z[i] 表示后缀 s[i:] 与 s 的 LCP（最长公共前缀）长度，其中 s[i:] 表示从 s[i] 到 s[n−1] 的子串。

遍历 words，对于 word=words[i]，构造字符串

s=word+#+target

中间插入 # 目的是避免 z[i] 超过 word 的长度。

计算 s 的 z 数组。设 m 为 word 的长度加一，那么 target[i:] 与 word 的最长公共前缀，就是 z[m+i]。用 z[m+i] 更新 maxJumps[i] 的最大值。

class Solution {
    vector<int> calc_z(string s) {
        int n = s.length();
        vector<int> z(n);
        int box_l = 0, box_r = 0; // z-box 左右边界（闭区间）
        for (int i = 1; i < n; i++) {
            if (i <= box_r) {
                z[i] = min(z[i - box_l], box_r - i + 1);
            }
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
                box_l = i;
                box_r = i + z[i];
                z[i]++;
            }
        }
        return z;
    }

    // 桥的概念，见我在 45 或 1326 题下的题解
    int jump(vector<int>& max_jumps) {
        int ans = 0;
        int cur_r = 0; // 已建造的桥的右端点
        int nxt_r = 0; // 下一座桥的右端点的最大值
        for (int i = 0; i < max_jumps.size(); i++) {
            nxt_r = max(nxt_r, i + max_jumps[i]);
            if (i == cur_r) { // 到达已建造的桥的右端点
                if (i == nxt_r) { // 无论怎么造桥，都无法从 i 到 i+1
                    return -1;
                }
                cur_r = nxt_r; // 造一座桥
                ans++;
            }
        }
        return ans;
    }

public:
    int minValidStrings(vector<string>& words, string target) {
        int n = target.length();
        vector<int> max_jumps(n);
        for (auto& word : words) {
            vector<int> z = calc_z(word + "#" + target);
            int m = word.length() + 1;
            for (int i = 0; i < n; i++) {
                max_jumps[i] = max(max_jumps[i], z[m + i]);
            }
        }
        return jump(max_jumps);
    }
};

复杂度分析

  • 时间复杂度：O(L+nm)，其中 n 是 target 的长度，m 是 words 的长度，L 是 words 中所有字符串的长度之和。
  • 空间复杂度：O(l+n)。其中 l 是 words[i] 的长度。

方法二：字符串哈希

写法一：二分

预处理每个 words[i] 的每个前缀的字符串哈希值，按照前缀长度分组，保存到不同的集合中。每个集合保存的是相同前缀长度的哈希值。

由于 words 的长度至多为 100，所以每个集合至多保存 100 个哈希值，根据生日攻击理论，单模哈希绰绰有余，碰撞概率很小。

然后对于每个 i，二分求出 maxJumps[i]。

二分的 check(mid) 函数怎么写？判断从 target[i] 开始的长为 mid 的子串，哈希值是否在集合中。

具体请看 本题视频讲解 第四题，欢迎点赞关注~

class Solution {
public:
    int minValidStrings(vector<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]
        const int MOD = 1'070'777'777;
        mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
        const int BASE = uniform_int_distribution<>(8e8, 9e8)(rng); // 随机 base，防止 hack
        vector<int> pow_base(n + 1); // pow_base[i] = base^i
        vector<int> pre_hash(n + 1); // 前缀哈希值 pre_hash[i] = hash(s[:i])
        pow_base[0] = 1;
        for (int i = 0; i < n; i++) {
            pow_base[i + 1] = (long long) pow_base[i] * BASE % MOD;
            pre_hash[i + 1] = ((long long) pre_hash[i] * BASE + target[i]) % MOD; // 秦九韶算法计算多项式哈希
        }
        // 计算 target[l] 到 target[r-1] 的哈希值
        auto sub_hash = [&](int l, int r) {
            return ((pre_hash[r] - (long long) pre_hash[l] * pow_base[r - l]) % MOD + MOD) % MOD;
        };

        int max_len = 0;
        for (auto& w : words) {
            max_len = max(max_len, (int) w.length());
        }
        vector<unordered_set<int>> sets(max_len);
        for (auto& w : words) {
            long long h = 0;
            for (int j = 0; j < w.size(); j++) {
                h = (h * BASE + w[j]) % MOD;
                sets[j].insert(h); // 注意 j 从 0 开始
            }
        }

        auto max_jump = [&](int i) -> int {
            // 开区间二分，left 一定满足要求，right 一定不满足要求
            int left = 0, right = min(n - i, max_len) + 1;
            while (left + 1 < right) {
                int mid = (left + right) / 2;
                (sets[mid - 1].contains(sub_hash(i, i + mid)) ? left : right) = mid;
            }
            return left;
        };

        int ans = 0;
        int cur_r = 0; // 已建造的桥的右端点
        int nxt_r = 0; // 下一座桥的右端点的最大值
        for (int i = 0; i < n; i++) {
            nxt_r = max(nxt_r, i + max_jump(i));
            if (i == cur_r) { // 到达已建造的桥的右端点
                if (i == nxt_r) { // 无论怎么造桥，都无法从 i 到 i+1
                    return -1;
                }
                cur_r = nxt_r; // 造一座桥
                ans++;
            }
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度：O(L+nlogn)，其中 n 是 target 的长度，L 是 words 中所有字符串的长度之和。
  • 空间复杂度：O(L+n)。

写法二：双指针

用双指针更新代码中的 nxtR：

  • 外层循环枚举 i，内层循环右移 nxtR。
  • 对于 target 的下标从 i 到 nxtR 的子串，如果其哈希值在哈希表中，那么把 nxtR 加一。
class Solution {
public:
    int minValidStrings(vector<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]
        const int MOD = 1'070'777'777;
        mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
        const int BASE = uniform_int_distribution<>(8e8, 9e8)(rng); // 随机 base，防止 hack
        vector<int> pow_base(n + 1); // pow_base[i] = base^i
        vector<int> pre_hash(n + 1); // 前缀哈希值 pre_hash[i] = hash(s[:i])
        pow_base[0] = 1;
        for (int i = 0; i < n; i++) {
            pow_base[i + 1] = (long long) pow_base[i] * BASE % MOD;
            pre_hash[i + 1] = ((long long) pre_hash[i] * BASE + target[i]) % MOD; // 秦九韶算法计算多项式哈希
        }
        // 计算 target[l] 到 target[r-1] 的哈希值
        auto sub_hash = [&](int l, int r) {
            return ((pre_hash[r] - (long long) pre_hash[l] * pow_base[r - l]) % MOD + MOD) % MOD;
        };

        int max_len = 0;
        for (auto& w : words) {
            max_len = max(max_len, (int) w.length());
        }
        vector<unordered_set<int>> sets(max_len);
        for (auto& w : words) {
            long long h = 0;
            for (int j = 0; j < w.size(); j++) {
                h = (h * BASE + w[j]) % MOD;
                sets[j].insert(h); // 注意 j 从 0 开始
            }
        }

        int ans = 0;
        int cur_r = 0; // 已建造的桥的右端点
        int nxt_r = 0; // 下一座桥的右端点的最大值
        for (int i = 0; i < n; i++) {
            while (nxt_r < n && nxt_r - i < max_len && sets[nxt_r - i].contains(sub_hash(i, nxt_r + 1))) {
                nxt_r++;
            }
            if (i == cur_r) { // 到达已建造的桥的右端点
                if (i == nxt_r) { // 无论怎么造桥，都无法从 i 到 i+1
                    return -1;
                }
                cur_r = nxt_r; // 造一座桥
                ans++;
            }
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度：O(L+n)，其中 n 是 target 的长度，L 是 words 中所有字符串的长度之和。
  • 空间复杂度：O(L+n)。

方法三：AC 自动机优化 DP

看示例 1，对比以下两个 target 的前缀：

  • aabcd，需要连接 2 个 words[i] 的前缀 aa 和 bcd。
  • aab，需要连接多少个前缀？可以肯定的是，答案一定不会比 2 还大，因为我们把 aabcd 末尾的 cd 去掉就可以得到 aab。这仍然是 2 个前缀的连接。

根据上述讨论，如果用 f[i] 表示 target 的长为 i 的前缀需要连接的最少字符串数量，那么 f[i]≤f[i+1] 一定成立。

既然 f 是有序数组，那么对于 f[i]，我们只需要知道最小的 j，满足从 target[j] 到 target[i−1] 是某个 words[i] 的前缀。

也就是说，匹配的 words[i] 的前缀要尽量长。这正是 AC 自动机的应用。原理见 OI Wiki。学习之前推荐先看看我的 KMP 原理讲解。

算出了 j，那么有

f[i]=f[j]+1

初始值 f[0]=0。

答案为 f[n]。

如果 AC 自动机没法匹配任何 words[i] 的非空前缀，返回 −1。

// 从根到 node 的字符串是某个（某些）words[i] 的前缀
struct Node {
    Node* son[26]{};
    Node* fail; // 当 cur.son[i] 不能匹配 target 中的某个字符时，cur.fail.son[i] 即为下一个待匹配节点（等于 root 则表示没有匹配）
    int len; // 从根到 node 的字符串的长度，也是 node 在 trie 中的深度

    Node(int len) : len(len) {}
};

struct AhoCorasick {
    Node* root = new Node(0);

    void put(string& s) {
        auto cur = root;
        for (char b : s) {
            b -= 'a';
            if (cur->son[b] == nullptr) {
                cur->son[b] = new Node(cur->len + 1);
            }
            cur = cur->son[b];
        }
    }

    void build_fail() {
        root->fail = root;
        queue<Node*> q;
        for (auto& son : root->son) {
            if (son == nullptr) {
                son = root;
            } else {
                son->fail = root; // 第一层的失配指针，都指向根节点 ∅
                q.push(son);
            }
        }
        // BFS
        while (!q.empty()) {
            auto cur = q.front();
            q.pop();
            for (int i = 0; i < 26; i++) {
                auto& son = cur->son[i];
                if (son == nullptr) {
                    // 虚拟子节点 cur.son[i]，和 cur.fail.son[i] 是同一个
                    // 方便失配时直接跳到下一个可能匹配的位置（但不一定是某个 words[k] 的最后一个字母）
                    son = cur->fail->son[i];
                    continue;
                }
                son->fail = cur->fail->son[i]; // 计算失配位置
                q.push(son);
            }
        }
    }
};

class Solution {
public:
    int minValidStrings(vector<string>& words, string target) {
        AhoCorasick ac;
        for (auto& w : words) {
            ac.put(w);
        }
        ac.build_fail();

        int n = target.length();
        vector<int> f(n + 1);
        auto cur = ac.root;
        for (int i = 0; i < n; i++) {
            // 如果没有匹配相当于移动到 fail 的 son[target[i]-'a']
            cur = cur->son[target[i] - 'a'];
            // 没有任何字符串的前缀与 target[..i] 的后缀匹配
            if (cur == ac.root) {
                return -1;
            }
            f[i + 1] = f[i + 1 - cur->len] + 1;
        }
        return f[n];
    }
};

复杂度分析

  • 时间复杂度：O(L∣Σ∣+n)，其中 n 是 target 的长度，L 是 words 中所有字符串的长度之和，∣Σ∣ 是字符集合的大小，本题字符均为小写字母，所以 ∣Σ∣=26。如果把数组替换成哈希表，可以做到 O(L+n) 的时间复杂度。
  • 空间复杂度：O(L∣Σ∣+n)。