Leecode刷题C++之形成目标字符串需要的最少字符串数①

执行结果:通过

执行用时和内存消耗如下：

代码如下： 

class Solution {
public:
    int minValidStrings(vector<string>& words, string target) {
        auto prefix_function = [](const string& word, const string& target) -> vector<int> {
            string s = word + '#' + target;
            int n = s.size();
            vector<int> pi(n, 0);
            for (int i = 1; i < n; i++) {
                int j = pi[i - 1];
                while (j > 0 && s[i] != s[j]) {
                    j = pi[j - 1];
                }
                if (s[i] == s[j]) {
                    j++;
                }
                pi[i] = j;
            }
            return pi;
        };

        int n = target.size();
        vector<int> back(n, 0);
        for (const string& word : words) {
            vector<int> pi = prefix_function(word, target);
            int m = word.size();
            for (int i = 0; i < n; i++) {
                back[i] = max(back[i], pi[m + 1 + i]);
            }
        }

        vector<int> dp(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            dp[i] = 1e9;
        }
        for (int i = 0; i < n; i++) {
            dp[i + 1] = dp[i + 1 - back[i]] + 1;
            if (dp[i + 1] > n) {
                return -1;
            }
        }
        return dp[n];
    }
};

解题思路：

这段代码的目的是为了解决一个特定的问题：给定一个字符串数组 words 和一个目标字符串 target，找出最小的字符串数量，使得从这些字符串中选取若干（可以重复选取）并按任意顺序拼接起来，能够形成一个新的字符串，这个新字符串包含 target 作为其子串，并且新字符串中不包含任何除 target 之外的字符。如果无法形成这样的字符串，则返回 -1。

解题思路可以分为以下几个步骤：

1. 定义前缀函数（prefix_function）：
   • 这个函数用于计算一个单词 word 和目标字符串 target 的最长相同前缀后缀数组（也称为部分匹配表或 π 表）。
   • 它通过将 word 和 target 连接，并在中间插入一个特殊字符（如 #），来避免 word 和 target 的重叠部分在计算时被误认为是匹配部分。
   • 然后，它使用 KMP（Knuth-Morris-Pratt）算法的核心逻辑来计算这个 π 表。
2. 计算每个单词相对于 target 的最大可重叠后缀长度：
   • 对于 words 数组中的每个单词，使用前缀函数计算其与 target 的 π 表。
   • 对于每个单词，通过 π 表找到从单词末尾开始，能与 target 开头最大匹配的长度，并更新一个 back 数组，该数组记录了在每个 target 的位置上，通过某个单词能匹配的最大长度。
3. 动态规划求解最小字符串数量：
   • 使用一个动态规划数组 dp，其中 dp[i] 表示形成长度为 i 的 target 子串所需的最小字符串数量。
   • 初始化 dp 数组，除了 dp[0]（形成空字符串需要 0 个字符串）之外，其他都设置为一个非常大的数（这里用 1e9），表示当前无法形成。
   • 遍历 target 的每个位置，使用 back 数组的信息更新 dp 数组。具体来说，如果能够通过前面的某些字符串匹配掉 target 的前 back[i] 个字符，则形成长度为 i+1 的子串所需的最小字符串数量等于形成长度为 i+1-back[i] 的子串所需的最小数量加 1。
   • 如果在任何时候 dp[i+1] 的值超过了 target 的长度，说明无法通过拼接形成完整的 target，返回 -1。
4. 返回结果：
   • 遍历完成后，dp[n]（其中 n 是 target 的长度）就是形成完整 target 所需的最小字符串数量。