สมมติว่าเรามีสตริง s เราต้องลบตัวอักษรที่เคยเกิดขึ้นมาก่อนหน้านี้แล้ว และคืนค่าสตริงที่ลดรูปแล้ว ในการแก้ปัญหานี้ เราจะใช้ Ordered Dictionary เพื่อรักษาลำดับการแทรกของตัวอักษร ค่าจะเป็นความถี่ของตัวอักษรเหล่านั้น แต่ค่าความถี่ไม่สำคัญในที่นี้ หลังจากสร้าง dictionary แล้ว เราสามารถนำ keys มารวมกันเพื่อได้สตริงผลลัพธ์
ตัวอย่างเช่น หาก s = "cabbbaadac" ผลลัพธ์จะเป็น "cabd"
ขั้นตอนการแก้ปัญหา
- d := dictionary ที่เก็บ keys ตามลำดับการแทรก (OrderedDict)
- สำหรับแต่ละตัวอักษร c ใน s:
- ถ้า c ไม่อยู่ใน d: d[c] := 0
- d[c] := d[c] + 1
- รวม keys ตามลำดับที่ถูกต้องเพื่อสร้างสตริงผลลัพธ์และคืนค่า
ตัวอย่างโค้ด
from collections import OrderedDict
def solve(s):
d = OrderedDict()
for c in s:
if c not in d:
d[c] = 0
d[c] += 1
return ''.join(d.keys())
s = "cabbbaadac"
print(solve(s))
อินพุต
"cabbbaadac"
เอาต์พุต
cabd
