在C ++中标记序列

假设我们要使目标字符串为小写字母。

首先，我们将序列设为n'？' 标记（n是目标字符串的长度）。我们也有一个小写字母的邮票。

在每个回合中，我们都可以将邮票放置在序列上，并用该邮票中的相应字母替换中的每个字母。您最多可以转10 * n转。例如，假设初始序列为“ ????????”，且戳记为“ abc”，那么我们可以在第一个字符串中输入“ abc ??”，“？abc？”，“ ?? abc”之类的字符串转。

如果可以对序列进行标记，则返回索引数组，并在每次旋转时标记最左边的字母。如果那不可能，则返回一个空数组。因此，当序列为“ ababc”且标记为“ abc”时，答案可以像[0，2]，因为我们可以像“ ?????”那样形成 ->“ abc ??” ->“ ababc”。

因此，如果输入类似于stamp =“ abcd”，target =“ abcdbcd”，则输出将为[3,0]

为了解决这个问题，我们将遵循以下步骤-

• 定义数组ret

• 好的：=真

• n：=印章大小

• tsz：= 0

• 当ok不为零时，请-

• 对于初始化i：= 0，当i <=印记大小时，更新（将i增加1），执行-

• 好的：=真

• x：= x + sz

• 在ret的末尾插入pos

• 从位置pos到pos +标记大小用“ *”填充目标。

• pos：= newStamp在目标中的索引

• newStamp：=长度为i的'*'字符串+从索引i到sz-1的图章子字符串+大小与图章大小相同的'*'字符串

• pos：= newStamp在目标中的索引

• 当pos存在于目标中时，执行-

• 好的：=假

• x：= 0

• 对于初始化sz：=戳的大小，当sz> 0时，更新（将sz减1），执行-

• tsz：= tsz + x

• 反转数组ret

• 返回（如果tsz与目标大小相同，则返回，否则返回一个空白数组）

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   } cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> movesToStamp(string stamp, string target) {
      vector<int> ret;
      bool ok = true;
      int n = stamp.size();
      int tsz = 0;
      while (ok) {
         ok = false;
         int x = 0;
         for (int sz = stamp.size(); sz > 0; sz--) {
            for (int i = 0; i <= stamp.size() - sz; i++) {
               string newStamp = string(i, '*') +
               stamp.substr(i, sz) + string(stamp.size() - sz - i, '*');
               int pos = target.find(newStamp);
               while (pos != string::npos) {
                  ok = true;
                  x += sz;
                  ret.push_back(pos);
                  fill(target.begin() + pos, target.begin() +
                  pos + stamp.size(), '*');
                  pos = target.find(newStamp);
               }
            }
         }
         tsz += x;
      }
      reverse(ret.begin(), ret.end());
      return tsz == target.size() ? ret : vector<int>();
   }
};
main(){
   Solution ob;
   print_vector(ob.movesToStamp("abcd", "abcdbcd"));
}

输入项

"abcd", "abcdbcd"

输出结果

[3, 0, ]