在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, ]