题目描述

你想要用小写字母组成一个目标字符串 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 = "aabcaca", target = "abca"
输出：[3,0,1]

算法1

(贪心)

前面所贴的邮票对后面贴的邮票是造成不了影响的
所以反过来思考，将target -> ??????

stamp的长子串是优于stamp的短子串,因为长字串能匹配得到的，那么包含该长字串的子符串一定能匹配得到,而反过来不一定.
举例来说：stamp 为 abcae时, abc能在target匹配得到, 那么ab一定能匹配得到，反过来则不一定
所以枚举stamp的子串, 按照stamp的子串长度从大到小的顺序在target找寻相同的字符串.
因为是要整个stamp一起贴,那么将子串补充为stamp的长度
举例来说：stamp 为 abcae时， abc补充为abc??, ae补充为???ae

在枚举stamp的子串，有可能完整地枚举一次并不能完全的找到,需要多次循环
举例来说
stamp = “uskh”
target = “uskhkhhskh”
完整的枚举一次过程中,得到
????khhskh
??????hskh
???????skh
因为在枚举?skh时, 对应的是target是 ????khhskh,
而在枚举???h后，对应的target是???????skh.

参考discuss:
https://leetcode.com/problems/stamping-the-sequence/discuss/189576/C%2B%2B-simple-greedy

C++ 代码

class Solution {
public:
vector<int> movesToStamp(string stamp, string target) {
    int m = stamp.length();
    int n = target.length();
    vector< int > goal;
    string pretarget;
    while( target != string( n, '*' ) ) {
        if( target == pretarget ) break;
        pretarget = target;
        for (int i = m; i > 0; --i) {
            for (int j = 0; j + i - 1 < m; ++j) {
                auto sub_stamp = string(j, '*') + stamp.substr(j, i) + string(m - i - j, '*');
                auto pos = target.find(sub_stamp);
                while (pos != string::npos) {
                    goal.push_back(pos);
                    fill(begin(target) + pos, begin(target) + pos + m, '*');
                    pos = target.find(sub_stamp);
                }
            }
        }
    }
    reverse( goal.begin(), goal.end() );
    return target == string( n, '*' ) ? goal : vector< int >();
}
};