สมมติว่าเรามีสตริง และเราต้องหาตัวอักษรที่ไม่ซ้ำตัวแรกในสตริง เช่นถ้าสตริงเป็น "people" ตัวอักษรแรกที่เกิดขึ้นครั้งเดียวคือ 'o' ดังนั้นดัชนีที่คืนค่าจะเป็น 2 ถ้าไม่มีตัวอักษรแบบนั้น ให้คืนค่า -1
วิธีการแก้ปัญหา
- สร้างแผนที่ความถี่ (frequency map) หนึ่งอัน
- สำหรับแต่ละตัวอักษร c ในสตริง:
- ถ้า c ไม่อยู่ใน frequency ให้แทรกลงไปใน frequency และตั้งค่าเป็น 1
- มิฉะนั้น ให้เพิ่มจำนวนใน frequency
- สแกนแผนที่ frequency ถ้าค่าของคีย์ใดเป็น 1 ให้คืนค่าคีย์นั้น มิฉะนั้นคืนค่า -1
ตัวอย่างโค้ด
class Solution(object):
def firstUniqChar(self, s):
"""
:type s: str
:rtype: int
"""
frequency = {}
for i in s:
if i not in frequency:
frequency[i] = 1
else:
frequency[i] += 1
for i in range(len(s)):
if frequency[s[i]] == 1:
return i
return -1
ob1 = Solution()
print(ob1.firstUniqChar("people"))
print(ob1.firstUniqChar("abaabba"))
อินพุต
"people" "abaabba"
เอาต์พุต
2 -1
