คำอธิบายโจทย์
เป้าหมาย: สร้าง target string จาก '?'*n โดยมี stamp string แต่ละครั้งทับ stamp ลงไปแทนที่ '?' ได้สูงสุด 10*n ครั้ง หาลำดับ index ที่ทับ stamp (leftmost) ได้ target หรือ empty array ถ้าไม่ได้
ตัวอย่าง
stamp="abcd", target="abcdbcd" → Output: [3,0]
??????? → stamp at 3: ???abcd → stamp at 0: abcdbcd
วิธีแก้ปัญหา
Greedy ย้อนกลับ (Reverse Simulation):
- เริ่มจาก target พยายามหา stamp ที่มี '*' (wildcard) ทับได้
- ลอง stamp ขนาดต่างๆ (substring ของ stamp) วางทุกตำแหน่ง
- เจอ match → แทนที่ด้วย '*', บันทึก position
- ทำซ้ำจน target กลายเป็น '*' ทั้งหมด
- กลับลำดับ positions → คำตอบ
การทำงานของโค้ด
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> movesToStamp(string stamp, string target) {
vector<int> ret;
bool ok = true;
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>();
}
};
int main() {
Solution ob;
auto ans = ob.movesToStamp("abcd", "abcdbcd");
for(int x : ans) cout << x << " ";
return 0;
}
อินพุต
"abcd", "abcdbcd"
เอาต์พุต
[3, 0]
