题目描述

你想要用小写字母组成一个目标字符串 target。

开始的时候，序列由 target.length 个 '?' 记号组成。而你有一个小写字母印章 stamp。

在每个回合，你可以将印章放在序列上，并将序列中的每个字母替换为印章上的相应字母。你最多可以进行 10 * target.length 个回合。

举个例子，如果初始序列为 “?????”，而你的印章 stamp 是 "abc"，那么在第一回合，你可以得到 “abc??”、”?abc?”、”??abc”。（请注意，印章必须完全包含在序列的边界内才能盖下去。）

如果可以印出序列，那么返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成。如果不能印出序列，就返回一个空数组。

例如，如果序列是 “ababc”，印章是 "abc"，那么我们就可以返回与操作 “?????” -> “abc??” -> “ababc” 相对应的答案 [0, 2]；

另外，如果可以印出序列，那么需要保证可以在 10 * target.length 个回合内完成。任何超过此数字的答案将不被接受。

样例

输入：stamp = "abc", target = "ababc"
输出：[0,2]
（[1,0,2] 以及其他一些可能的结果也将作为答案被接受）

输入：stamp = "abca", target = "aabcaca"
输出：[3,0,1]

注意

• 1 <= stamp.length <= target.length <= 1000
• stamp 和 target 只包含小写字母。

算法

(动态规划) $O(mn^2)$

(想法比较独特和复杂，希望对读者有所启发。)
假设 $n = stamp.length$，$m = target.length$。

1. 设 $f(i)=(00,01,10,11)$ 中的某个值，表示考虑了 target 前 $i$ 个字符后的状态。$f(i)=00$ 表示无法匹配；$f(i)=01$ 表示可以匹配，但在 $i$ 位置的 stamp 不完整，即 $i$ 之后的一些字符被 填充 $i$ 时的 stamp 填写了；$f(i)=10$ 表示可以匹配，且在 $i$ 位置的 stamp 完整，即到 $i$ 正好完成一个 stamp。$f(i)=11$ 表示 $f(i)=01 和 f(i)=10$ 都存在。
2. 转移时，考虑 target 的第 $i$ 个字符该如何被填写。首先考虑 target 上 $j$ 到 $i$ 的子串 $substr$（保证 $j$ 合法）。如果 $substr$ 在 stamp 中出现过，则找到若干个出现的位置 $k$。
3. 对于某个 $k$，若 $k$ 等于 0，即 $substr$ 是 stamp 的前缀，则若 $f(j-1) \ge 01$，当前位置就可以匹配，因为不管上一次的匹配情况，我们都可以直接覆盖。否则，必须要求 $f(j-1) \ge 10$，当前位置才可以匹配，因为这一次的填写的前缀需要被覆盖掉一部分，所以必须要求上一次是完整 stamp 匹配。若可以匹配，则更新 $f(i)$。如果 $substr$ 是 stamp 的后缀，则 $f(i) = f(i)$ | $10$，否则 $f(i) = f(i)$ | $01$。
4. 我们显然更喜欢 $10$，所以，一旦 $f(i) = 10$ 更新完成，直接结束转移即可。
5. 最后如果 $f(m) \ge 10$，则表明可以完成匹配，然后根据状态 dfs 构造答案即可，需要在转移时继续 $p$ 和 $s$ 数组以便于定位。

时间复杂度

• 状态数有 $m$ 个，每次需要枚举子串并且需要枚举子串的位置，故总共需要 $O(mn^2)$ 的时间，但常数非常小，可以通过。

C++ 代码

class Solution {
public:

    void dfs(int i, vector<int> &f, vector<int> &p, vector<int> &s, vector<int> &ans) {
        if (i == 0)
            return;
        int j = p[i];
        if (f[j] >= 2) {
            ans.push_back(i - s[i]);
            dfs(j, f, p, s, ans);
        }
        else {
            dfs(j, f, p, s, ans);
            ans.push_back(i - s[i]);
        }
    }

    vector<int> movesToStamp(string stamp, string target) {
        int n = stamp.length(), m = target.length();
        vector<int> ans;
        unordered_map<string, vector<int>> hash;

        for (int i = 0; i < n; i++)
            for (int j = i; j < n; j++)
                hash[stamp.substr(i, j - i + 1)].push_back(i);


        vector<int> f(m + 1, 0);
        vector<int> p(m + 1, -1), s(m + 1, -1);
        f[0] = 2;
        p[0] = -1;
        for (int i = 1; i <= m; i++) {
            for (int j = i - 1; j >= max(0, i - n); j--) {
                if (hash.find(target.substr(j, i - j)) != hash.end()) {
                    vector<int> t = hash[target.substr(j, i - j)];
                    for (int k = 0; k < t.size(); k++) {
                        if (t[k] + i - j == n) {
                            if (t[k] == 0) {
                                if (f[j] >= 1) {
                                    f[i] = f[i] | 2;
                                    p[i] = j;
                                    s[i] = t[k] + i - j;
                                }
                            }
                            else {
                                if (j != 0 && f[j] >= 2) {
                                    f[i] = f[i] | 2;
                                    p[i] = j;
                                    s[i] = t[k] + i - j;
                                }
                            }
                        }
                        else {
                            if (t[k] == 0) {
                                if (f[j] >= 1) {
                                    f[i] = f[i] | 1;
                                    p[i] = j;
                                    s[i] = t[k] + i - j;
                                }
                            }
                            else {
                                if (j != 0 && f[j] >= 2) {
                                    f[i] = f[i] | 1;
                                    p[i] = j;
                                    s[i] = t[k] + i - j;
                                }
                            }
                        }
                        if (f[i] >= 2)
                            break;
                    }
                }
                else {
                    break;
                }
                if (f[i] >= 2)
                    break;
            }
        }

        if (f[m] >= 2)
            dfs(m, f, p, s, ans);
        return ans;
    }
};