สมมติว่ามีรายการสตริงตัวพิมพ์เล็ก เราต้องหาคำนำหน้าที่ยาวที่สุดที่พบร่วมกัน
เช่น ถ้าอินพุตคือ ["antivirus", "anticlockwise", "antigravity"] ผลลัพธ์จะเป็น "anti"
ขั้นตอนการแก้ปัญหา
- เรียงรายการ words ตามตัวอักษร
- prefix := รายการใหม่, flag := 0
- for i ในช่วง 0 ถึง len(words[0])
- prefix.append(words[0][i])
- for j ใน words ถ้า j[i] != prefix[-1] prefix.pop(), flag := 1, break
- ถ้า flag == 1 break
- คืนค่าสตริงจากการต่อสมาชิกใน prefix
ตัวอย่างโค้ด
class Solution:
def solve(self, words):
words.sort()
prefix = []
flag = 0
for i in range(len(words[0])):
prefix.append(words[0][i])
for j in words:
if j[i] != prefix[-1]:
prefix.pop()
flag = 1
break
if flag == 1:
break
return ''.join(prefix)
ob = Solution()
words = ["antivirus", "anticlockwise", "antigravity"]
print(ob.solve(words))
อินพุต
["antivirus", "anticlockwise", "antigravity"]
เอาต์พุต
anti
