Сложность: hard
Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив
Пример:
Input: stamp = "abc", target = "ababc"
Output: [0,2]
👨💻 Алгоритм:
1⃣Инициализировать переменные:
s как массив символов '?', длиной target.length.
res как список для хранения результатов.
done как массив булевых значений для отслеживания того, какие позиции уже штампованы.
target как массив символов для удобства.
2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i.
Использовать функцию doStamp для штампования stamp в target начиная с индекса i.
Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length):
Перебрать все возможные начальные позиции для штампа.
Проверить, можно ли штамповать в текущей позиции.
Если можно, штамповать и добавить индекс в res.
3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив.
😎 Решение:
class Solution {
public:
vector<int> movesToStamp(string stamp, string target) {
vector<int> res;
vector<bool> done(target.size(), false);
string t = target;
string s = stamp;
int m = s.size(), n = t.size();
auto canStamp = [&](int i) {
for (int j = 0; j < m; j++) {
if (t[i + j] != '?' && t[i + j] != s[j]) {
return false;
}
}
return true;
};
auto doStamp = [&](int i) {
for (int j = 0; j < m; j++) {
t[i + j] = '?';
}
res.push_back(i);
done[i] = true;
};
bool changed = true;
while (changed) {
changed = false;
for (int i = 0; i <= n - m; i++) {
if (!done[i] && canStamp(i)) {
doStamp(i);
changed = true;
}
}
}
for (char c : t) {
if (c != '?') {
return {};
}
}
reverse(res.begin(), res.end());
return res;
}
};Ставь 👍 и забирай 📚 Базу знаний