LeetCode #438 Find All Anagrams: หน้าต่างเลื่อนชนะการ sort ทุกช่อง
น้องกายEngineering
โจทย์ Find All Anagrams in a String #438 ให้สตริง s กับแบบ p แล้วขอทุกดัชนีเริ่มต้นของช่วงใน s ที่เป็น anagram ของ p
แมวขี้เกียจ sort ทุกหน้าต่าง เทียบกับ p ที่ sort แล้ว — เข้าใจง่าย แต่ช้า
นากนับ ใช้ Counter / อาร์เรย์ความถี่เลื่อนหน้าต่าง — O(n)
Benchmark (เครื่องนี้)
สตริงยาวจาก 'cbaebabacd'*800, แบบ abc
| วิธี | เวลา |
|---|---|
| หน้าต่างเลื่อนทั้งสตริง | 1.99 ms |
| sort ทุกช่องบน s[:5000] | 1.24 ms (ช่วงสั้นกว่า; ทั้งสตริงจะช้ากว่ามาก) |
โค้ด
from collections import Counter
def find_anagrams(s: str, p: str):
need = Counter(p)
window = Counter()
missing = len(p)
left = 0
ans = []
for right, ch in enumerate(s):
window[ch] += 1
if window[ch] <= need[ch]:
missing -= 1
if right - left + 1 > len(p):
leftch = s[left]
if window[leftch] <= need[leftch]:
missing += 1
window[leftch] -= 1
left += 1
if missing == 0:
ans.append(left)
return ans
assert find_anagrams("cbaebabacd", "abc") == [0, 6]
print("ok")บารอนสรุป
สัมภาษณ์ให้อธิบายความถี่เลื่อนหน้าต่าง production ใช้แบบนับ ไม่ sort ซ้ำ
Recap
- หาทุกจุดเริ่ม anagram ของ p ใน s
- sort ทุกช่อง vs หน้าต่างเลื่อน O(n)
- Benchmark: เลื่อนหน้าต่าง ~2 ms บนสตริงยาวชุดทดสอบ