题目描述

给你一个字符串 target、一个字符串数组 words 以及一个整数数组 costs，这两个数组长度相同。

设想一个空字符串 s。

你可以执行以下操作任意次数（包括 零 次）：

• 选择一个在范围 [0, words.length - 1] 的索引 i。
• 将 words[i] 追加到 s。
• 该操作的成本是 costs[i]。

返回使 s 等于 target 的 最小 成本。如果不可能，返回 -1。

样例

输入： target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]

输出： 7

解释：

选择索引 1 并以成本 1 将 "abc" 追加到 s，得到 s = "abc"。
选择索引 2 并以成本 1 将 "d" 追加到 s，得到 s = "abcd"。
选择索引 4 并以成本 5 将 "ef" 追加到 s，得到 s = "abcdef"。

输入： target = "aaaa", words = ["z","zz","zzz"], costs = [1,10,100]

输出： -1

解释：

无法使 s 等于 target，因此返回 -1。

限制

• 1 <= target.length <= 5 * 10^4
• 1 <= words.length == costs.length <= 5 * 10^4
• 1 <= words[i].length <= target.length
• 所有 words[i].length 的总和小于或等于 5 * 10^4
• target 和 words[i] 仅由小写英文字母组成。
• 1 <= costs[i] <= 10^4

算法

(AC 自动机，动态规划) $O(n T + |\Sigma| \cdot \Sigma |w_i|)$

1. 对模式串构造 AC 自动机或字典图。
2. 然后对目标串进行动态规划，即在匹配模式串的过程中，如果遇到了模式串的结尾，则通过状态转移，用模式串开头的位置，更新当前位置的状态值。
3. 注意，有可能出现相同的模式串，此时需要存储代价最小的模式串的下标。
4. 为了避免沿着失败指针往上寻找的次数过多，需要新增一个失败指针 parent，用来存储最近一个是某个字符串结尾的失败节点。

时间复杂度

• 构造 AC 自动机的时间复杂度为 $O(|\Sigma| \cdot \Sigma |w_i|)$，其中 $|\Sigma|$ 时字符集的大小，这里为 $26$。
• 动态规划的状态数为 $O(n)$，转移时间 $T$ 取决于每次沿着失败指针往上寻找的次数。当所有模式串都是前缀包含关系，例如 $a$、$aa$、$aaa$ 等，以及目标串为全 $a$ 的极端情况下，失配匹配次数会退化到 $T = \min(n, \sqrt L)$。
• 故总时间复杂度为

(AC 自动机，动态规划) $O(n T + |\Sigma| \cdot \Sigma |w_i|)$。

空间复杂度

• 需要 $O(n + |\Sigma| \Sigma |w_i|)$ 的额外空间存储字典树和动态规划的状态。

C++ 代码（AC 自动机）

struct Node {
    Node *nxt[26], *fail, *parent;
    int idx;
    Node() {
        memset(nxt, 0, sizeof(nxt));
        idx = -1;
    }
};

class Solution {
private:
    Node *root;

    void insert(const string &w, int i, const vector<int> &costs) {
        Node *p = root;
        for (char c : w) {
            if (p->nxt[c - 'a'] == NULL)
                p->nxt[c - 'a'] = new Node();
            p = p->nxt[c - 'a'];
        }

        if (p->idx == -1 || costs[p->idx] > costs[i])
            p->idx = i;
    }

    void build() {
        queue<Node*> q;
        root->fail = root;
        root->parent = root;
        for (int i = 0; i < 26; i++)
            if (root->nxt[i]) {
                root->nxt[i]->fail = root;
                root->nxt[i]->parent = root;
                q.push(root->nxt[i]);
            }

        while (!q.empty()) {
            Node *u = q.front();
            q.pop();

            for (int i = 0; i < 26; i++) {
                if (u->nxt[i] == NULL)
                    continue;

                Node *p = u->fail;
                while (p != root && p->nxt[i] == NULL)
                    p = p->fail;

                if (p->nxt[i]) {
                    u->nxt[i]->fail = p->nxt[i];
                    if (p->nxt[i]->idx != -1) // parent 为了优化转移
                        u->nxt[i]->parent = p->nxt[i];
                    else
                        u->nxt[i]->parent = p->nxt[i]->parent;
                } else {
                    u->nxt[i]->fail = root;
                    u->nxt[i]->parent = root;
                }

                q.push(u->nxt[i]);
            }
        }
    }

public:
    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        const int n = target.size();
        const int m = words.size();
        const int INF = 1000000000;

        root = new Node();
        for (int i = 0; i < m; i++)
            insert(words[i], i, costs);

        build();

        vector<int> f(n + 1, INF);
        f[0] = 0;
        Node *p = root;
        for (int i = 1; i <= n; i++) {
            int c = target[i - 1] - 'a';
            while (p != root && p->nxt[c] == NULL)
                p = p->fail;

            if (p->nxt[c])
                p = p->nxt[c];

            Node *t = p;
            for (Node *t = p; t != root; t = t->parent) {
                int j = t->idx;
                if (j >= 0)
                    f[i] = min(f[i], f[i - words[j].size()] + costs[j]);
            }
        }

        if (f[n] == INF)
            return -1;

        return f[n];
    }
};

C++ 代码（字典图）

struct Node {
    Node *nxt[26], *fail, *parent;
    int idx;
    Node() {
        memset(nxt, 0, sizeof(nxt));
        idx = -1;
    }
};

class Solution {
private:
    Node *root;

    void insert(const string &w, int i, const vector<int> &costs) {
        Node *p = root;
        for (char c : w) {
            if (p->nxt[c - 'a'] == NULL)
                p->nxt[c - 'a'] = new Node();
            p = p->nxt[c - 'a'];
        }

        if (p->idx == -1 || costs[p->idx] > costs[i])
            p->idx = i;
    }

    void build() {
        queue<Node*> q;
        root->fail = root;
        root->parent = root;
        for (int i = 0; i < 26; i++)
            if (root->nxt[i]) {
                root->nxt[i]->fail = root;
                root->nxt[i]->parent = root;
                q.push(root->nxt[i]);
            } else {
                root->nxt[i] = root;
            }

        while (!q.empty()) {
            Node *u = q.front();
            q.pop();

            for (int i = 0; i < 26; i++) {
                if (u->nxt[i]) {
                    u->nxt[i]->fail = u->fail->nxt[i];
                    if (u->fail->nxt[i]->idx != -1) // parent 为了优化转移
                        u->nxt[i]->parent = u->fail->nxt[i];
                    else
                        u->nxt[i]->parent = u->fail->nxt[i]->parent;

                    q.push(u->nxt[i]);
                } else {
                    u->nxt[i] = u->fail->nxt[i];
                }
            }
        }
    }

public:
    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        const int n = target.size();
        const int m = words.size();
        const int INF = 1000000000;

        root = new Node();
        for (int i = 0; i < m; i++)
            insert(words[i], i, costs);

        build();

        vector<int> f(n + 1, INF);
        f[0] = 0;
        Node *p = root;
        for (int i = 1; i <= n; i++) {
            int c = target[i - 1] - 'a';
            p = p->nxt[c];

            for (Node *t = p; t != root; t = t->parent) {
                int j = t->idx;
                if (j >= 0)
                    f[i] = min(f[i], f[i - words[j].size()] + costs[j]);
            }
        }

        if (f[n] == INF)
            return -1;

        return f[n];
    }
};