ข้อ 71 · LC1268 Search Suggestions System (ระบบแนะนำคำค้น) 🟡

โจทย์ (LC1268): กำหนด array of string ชื่อ products และ string ชื่อ searchWord ให้ออกแบบระบบที่แนะนำชื่อสินค้าไม่เกิน 3 ชื่อจาก products หลังจากผู้ใช้พิมพ์ตัวอักษรแต่ละตัวของ searchWord สินค้าที่แนะนำต้องมี common prefix (คำนำหน้าร่วม) กับสิ่งที่พิมพ์มาแล้ว ถ้ามีมากกว่า 3 ชื่อที่ตรงเงื่อนไข ให้เลือก 3 ชื่อที่เรียงตาม lexicographical order (พจนานุกรม) น้อยที่สุด แล้ว return เป็น list of list ของคำแนะนำหลังพิมพ์ตัวอักษรแต่ละตัว

แนวทาง — ต้องใช้อะไร & คิดยังไง

ข้อนี้ใช้ trie ผสมกับการ sort (เรียง) ล่วงหน้า idea คือถ้า sort products ก่อนหนึ่งครั้ง แล้วค่อย insert ลง trie คำที่ผ่านแต่ละ node จะมาตาม lexicographic order อยู่แล้ว เราจึงเก็บแค่ 3 ตัวแรกที่แต่ละ node พอ

วิธีตรงไปตรงมาคือทุกครั้งที่พิมพ์ ก็ filter products ทั้งหมดที่ขึ้นต้นด้วย prefix แล้ว sort เอา 3 ตัวแรก ซึ่งทำงานซ้ำ ๆ และช้าเมื่อพิมพ์ยาว ๆ การเก็บ suggestions ไว้ที่แต่ละ node ตั้งแต่ตอนสร้าง trie ทำให้ตอนตอบแค่ traverse (เดินไล่) ตาม prefix แล้วหยิบออกมาได้ทันที

1. sort products ก่อนหนึ่งครั้ง
2. insert แต่ละคำลง trie ไล่ตัวอักษร ระหว่าง traverse ให้ append (ต่อท้าย) คำนั้นเข้า node.suggestions ถ้ายังเก็บไม่ถึง 3 ตัว
3. ตอบ searchWord: traverse ตามตัวอักษรที่พิมพ์ทีละตัวจาก root ถ้ายัง traverse ได้ก็หยิบ node.suggestions ใส่ผลลัพธ์
4. ถ้าหลุดเส้นทางเมื่อไร ตั้ง node = None แล้ว append [] ให้ตัวอักษรที่เหลือทั้งหมด

class TrieNode:
    def __init__(self):
        self.children = {}
        self.suggestions = []   # สินค้าไม่เกิน 3 ตัวแรก (เรียงแล้ว) ที่ผ่าน node นี้

def suggested_products(products, searchWord):
    root = TrieNode()

    # sort ก่อน เพื่อให้คำที่ใส่เข้า trie มาตามลำดับพจนานุกรม
    for product in sorted(products):
        node = root
        for ch in product:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
            # เก็บได้แค่ 3 ตัวแรกพอ (มาตามลำดับ sort อยู่แล้ว)
            if len(node.suggestions) < 3:
                node.suggestions.append(product)

    result = []
    node = root
    for ch in searchWord:
        # ถ้ายังเดินตาม prefix ได้ ก็หยิบ suggestions ที่ node นั้น
        if node and ch in node.children:
            node = node.children[ch]
            result.append(node.suggestions)
        else:
            # หลุดเส้นทางแล้ว ที่เหลือไม่มีคำแนะนำ
            node = None
            result.append([])
    return result

print(suggested_products(
    ["mobile", "mouse", "moneypot", "monitor", "mousepad"], "mouse"))
# [['mobile','moneypot','monitor'], ['mobile','moneypot','monitor'],
#  ['mouse','mousepad'], ['mouse','mousepad'], ['mouse','mousepad']]

[['mobile', 'moneypot', 'monitor'], ['mobile', 'moneypot', 'monitor'], ['mouse', 'mousepad'], ['mouse', 'mousepad'], ['mouse', 'mousepad']]