LeetCode936题目

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

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

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

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

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

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

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

1 <= stamp.length <= target.length <= 1000

stamp 和 target 只包含小写字母。

分析

自己想出来的笨办法，时间复杂度较低。公认的方法是拓扑排序。

代码

class Solution {
public:
    vector<int> movesToStamp(string stamp, string target) {
        int iWindowCount = target.length() - stamp.length() + 1;
        m_strDebug = target;
        unordered_map<int, unordered_set<int>> vNotSame;
        std::unordered_multiset<int> setNeed;
        for (int i = 0; i < target.size(); i++)
        {
            setNeed.emplace(i);
        }
        vector<vector<int>> vDirect(target.length());
        std::vector<int> vQue;
        for (int i = 0; i < iWindowCount; i++)
        {
            for (int j = 0; j < stamp.size(); j++)
            {
                if (stamp[j] != target[i + j])
                {
                    vNotSame[i].emplace(i + j);
                    vDirect[i + j].emplace_back(i);
                }
            }
            if (!vNotSame.count(i))
            {
                vQue.emplace_back(i);
            }
        }

        int index = 0;
        while (setNeed.size() && (index < vQue.size()))
        {
            const auto cur = vQue[index];
            index++;
            for (int i = 0; i < stamp.length(); i++)
            {
                setNeed.erase(i + cur);
                assert(('?' == m_strDebug[i + cur]) || (m_strDebug[i + cur] == stamp[i]));
                m_strDebug[i + cur] = '?';
                for (const auto& n : vDirect[i + cur])
                {
                    if (!vNotSame.count(n))
                    {
                        continue;
                    }
                    vNotSame[n].erase(i + cur);
                    if (0 == vNotSame[n].size())
                    {
                        vQue.emplace_back(n);
                        vNotSame.erase(n);
                    }
                }
            }
            //    CConsole::Out(m_strDebug);
        }

        vector<int> vRet(vQue.begin(), vQue.begin() + index);
        return setNeed.size() ? vector<int>{} : vector<int>(vRet.rbegin(), vRet.rend());
    }
    string m_strDebug;
};