C++算法：戳印序列原理及实现二

题目

你想要用小写字母组成一个目标字符串 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 只包含小写字母。

分析

倒着处理，把target变成???，某个字符系列除已经变成???问号的部分，其它部分和印章全部相同。

代码

class Solution {
public:
vector movesToStamp(string stamp, string target) {
int m = stamp.size();
int n = target.size();
//vCanLast[i]为x表示。target[i]到target[i+m-1] 共有x个字符和stamp不同。完全相同，为0表示，在i除及后续盖章，
//可以保证target[i]到target[i+m-1] 可以达成目标
//利用拓扑排序解决
m_iWindowNum = n - m + 1;
vector vNeedModify(m_iWindowNum, m);
vector<vector> vDirect(n);
std::stack sta;
for (int i = 0; i < m_iWindowNum; i++)
{
for (int j = 0; j < m; j++)
{
if (target[i + j] == stamp[j])
{
vNeedModify[i]–;
if (0 == vNeedModify[i])
{
sta.push(i);
}
}
else
{
vDirect[i + j].push_back(i);
}
}
}

vector<int> vHasModify(n);
   vector<int> ret;
   while (sta.size())
   {
     int iCur = sta.top();
     sta.pop();
     ret.push_back(iCur);
     for (int j = 0; j < m; j++)
     {
       if (vHasModify[iCur + j])
       {
         continue;
       }
       vHasModify[iCur + j] = 1;
       for (auto& dd : vDirect[iCur + j])
       {
         vNeedModify[dd]--;
         if (0 == vNeedModify[dd])
         {
           sta.push(dd);
         }
       }
     }
   }
   if (n == std::accumulate(vHasModify.begin(), vHasModify.end(), 0))
   {
     return vector<int>(ret.rbegin(), ret.rend());
   }
   return vector<int>();
 }
 int m_iWindowNum;//滑动窗口数量

};

其它

视频课程

如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。

https://edu.csdn.net/course/detail/38771

我的其它课程

[https://edu.csdn.net/lecturer/6176]

(https://edu.csdn.net/lecturer/6176)

测试环境

win7 VS2019 C++17

相关下载

doc版文档，排版好

https://download.csdn.net/download/he_zhidan/88348653