ได้รายการคำแทนพจนานุกรม หาคำที่ยาวที่สุดที่สร้างได้ทีละตัวอักษรจากคำอื่นในพจนานุกรม (คำนำหน้าทุกตัวต้องมีในพจนานุกรม) หากหลายคำ คืนคำที่เรียงลำดับเล็กซิโคกราฟิกน้อยที่สุด
ตัวอย่าง
["h","he","hel","hell","hello"] → "hello" (h→he→hel→hell→hello ทุกคำนำหน้ามีอยู่)
ขั้นตอนการแก้ปัญหา (Trie)
- สร้าง Trie ใส่คำทุกคำ
- แต่ละโหนดเก็บว่าเป็นปลายคำหรือไม่
- ค้นหาคำที่: ทุกคำนำหน้ามีอยู่ใน Trie (เป็นคำสมบูรณ์)
- เลือกคำที่ยาวที่สุด, ถ้าเท่ากันเลือกเรียงลำดับน้อยที่สุด
การติดตั้งใน Python
class Solution:
def longestWord(self, words):
self.trie = {}
def insert(word):
node = self.trie
for c in word:
if c not in node:
node[c] = {'#': False}
node = node[c]
node['#'] = True
def search(word):
node = self.trie
for c in word:
if '#' in node and not node['#']:
return False
node = node[c]
return node['#']
for w in words:
insert(w)
ans = ""
for w in words:
if search(w) and (len(w) > len(ans) or (len(w) == len(ans) and w < ans)):
ans = w
return ans
ob = Solution()
print(ob.longestWord(["h","he","hel","hell","hello"])) # hello
อินพุต / เอาต์พุต
Input: ["h","he","hel","hell","hello"] Output: hello
