มีสตริงเป้าหมาย t เริ่มต้นเป็น ? ทุกตัว มีแสตมป์ s แต่ละครั้งวางแสตมป์ทับ ? ได้ ต้องหาลำดับดัชนีที่วางแสตมป์ (ซ้ายสุดของแสตมป์) ถ้าไม่ได้คืนลิสต์ว่าง
ตัวอย่าง: s="abcd", t="abcdbcd" ผลลัพธ์ [3,0]
วิธีแก้ปัญหา (ย้อนกลับ: จากเป้าหมายไปสู่ทั้งหมดเป็น ?)
- ถ้า
len(s)==1กรณีพิเศษ - วนลูปจน
tกลายเป็นทั้งหมด?:- ลองทุกตำแหน่งและความยาวของส่วนที่ตรงกับ
s(ส่วนที่เหลือเป็น?) - แทนที่ส่วนที่เจอเป็น
?บันทึกตำแหน่ง
- ลองทุกตำแหน่งและความยาวของส่วนที่ตรงกับ
- คืนลำดับย้อนกลับ
ตัวอย่างโค้ด
def solve(s, t):
if len(s) == 1:
return [i for i in range(len(t))] if all(c==s[0] for c in t) else []
ans = []
while t != "?" * len(t):
tmp = t
for i in range(len(s)):
for j in reversed(range(i+1, len(s)+1)):
search = "?"*i + s[i:j] + "?"*(len(s)-j)
while t.find(search) != -1:
ans.append(t.find(search))
t = t.replace(search, "?"*len(s), 1)
if t == "?" * len(t): break
if t == "?" * len(t): break
if tmp == t: return []
return ans[::-1]
s = "abcd"
t = "abcdbcd"
print(solve(s, t))
อินพุต
"abcd", "abcdbcd"
เอาต์พุต
[3,0]
