สมมติว่าเรามีสตริง s และ t ความยาวเท่ากัน พิจารณาการดำเนินการเลือกสอง index ในสตริง (อาจเท่ากันได้) แล้วสลับตัวอักษร ต้องการทราบว่าสามารถทำให้ s และ t เหมือนกันได้ด้วยการสลับสูงสุด 1 ครั้งบนสตริงใดสตริงหนึ่งหรือไม่
เช่น s = "hello" t = "hlelo" ผลลัพธ์คือ True เพราะสลับ 'e' และ 'l' ใน s หรือ t จะทำให้เท่ากัน
ขั้นตอนการแก้ปัญหา
- max_diffs = 2, diffs = 0
- st = set(), st2 = set() (เก็บตัวอักษรที่ไม่ซ้ำใน s และ t)
- วนลูป i จาก 0 ถึง len(s)-1:
- ถ้า s[i] != t[i]: diffs += 1
- เพิ่ม s[i] เข้า st, t[i] เข้า st2
- ถ้า diffs > max_diffs: คืน False
- คืน True ถ้า (diffs == 0 หรือ diffs == 2) และ len(st) == len(st2) และ st == st2 มิฉะนั้น False
ตัวอย่างโค้ด
def solve(s, t):
max_diffs = 2
diffs = 0
st = set()
st2 = set()
for i in range(len(s)):
if s[i] != t[i]:
diffs += 1
if s[i] not in st:
st.add(s[i])
if t[i] not in st2:
st2.add(t[i])
if diffs > max_diffs:
return False
return (diffs == 0 or diffs == 2) and len(st) == len(st2) and st == st2
s = "hello"
t = "hlelo"
print(solve(s, t))
ข้อมูลเข้า
"hello", "hlelo"
ข้อมูลออก
True
