LeetCode 14 Longest Common Prefix: หดคำตั้งต้นจนทุกคำยอมรับ

โจทย์ Longest Common Prefix ให้หาสตริงยาวที่สุดที่เป็นคำนำหน้าของทุกคำ ถ้าอักษรตัวแรกไม่ตรงกันให้คืนข้อความว่างครับ

สรุปโจทย์ด้วยคำของเรา

Prefix ต้องเริ่มที่ตำแหน่งศูนย์ของทุกคำ จึงต่างจาก substring ที่อยู่กลางคำได้ เราต้องหยุดทันทีเมื่อคำใดสั้นกว่าหรือมีอักษรไม่ตรง ไม่จำเป็นต้องสร้าง trie เสมอเพราะโจทย์ขอคำตอบเดียวจากชุดคงที่

วิธีที่ 1: horizontal shrink

เริ่ม prefix เป็นคำแรก แล้ววนคำถัดไป ถ้าคำนั้นไม่ขึ้นต้นด้วย prefix ให้ตัดท้าย prefix จนกว่าจะตรงหรือว่าง

• เวลาแย่สุด O(S) โดย S คือจำนวนอักษรรวมที่ตรวจ แม้อาจตรวจบาง prefix ซ้ำ
• หน่วยความจำขึ้นกับ string slicing; แนวคิดเพิ่ม O(1)
• อ่านง่ายและรองรับ iterable ทีละคำได้

วิธีที่ 2: vertical scan

เดินตำแหน่งของคำแรก แล้วเทียบอักษรตำแหน่งเดียวกันกับทุกคำ ถ้าคำใดหมดหรือไม่ตรง ให้คืน prefix ก่อนหน้า

• เวลา O(S) และหยุดเร็วเมื่อ mismatch อยู่ต้นคำ
• หน่วยความจำเพิ่ม O(1)
• index boundary ชัด แต่ต้องมี list ที่วนซ้ำได้

วิธีที่ 3: sort แล้วเทียบคำแรกกับคำสุดท้าย

หลังเรียง lexicographically คำที่ต่างกันที่สุดจะอยู่ปลายสองข้าง Common prefix ของทั้งชุดจึงเท่ากับของคำแรกและคำสุดท้าย

• เวลา O(n log n × L) จาก sorting โดยประมาณ
• อาจแก้ลำดับ input ถ้า sort in place; ใช้ min/max เพื่อไม่ต้อง sort ทั้งชุดได้
• กระชับ แต่ทำงานมากเกินไปถ้าต้องการ prefix อย่างเดียว

import unittest


def prefix_shrink(words):
    if not words:
        return ""
    prefix = words[0]
    for word in words[1:]:
        while prefix and not word.startswith(prefix):
            prefix = prefix[:-1]
        if not prefix:
            return ""
    return prefix


def prefix_vertical(words):
    if not words:
        return ""
    for index, character in enumerate(words[0]):
        for word in words[1:]:
            if index >= len(word) or word[index] != character:
                return words[0][:index]
    return words[0]


def prefix_extremes(words):
    if not words:
        return ""
    first, last = min(words), max(words)
    index = 0
    while index < min(len(first), len(last)) and first[index] == last[index]:
        index += 1
    return first[:index]


class PrefixTests(unittest.TestCase):
    def check(self, words, expected):
        self.assertEqual(prefix_shrink(words), expected)
        self.assertEqual(prefix_vertical(words), expected)
        self.assertEqual(prefix_extremes(words), expected)

    def test_shared_and_missing_prefix(self):
        self.check(["flower", "flow", "flight"], "fl")
        self.check(["dog", "racecar", "car"], "")

    def test_empty_short_and_unicode(self):
        self.check([], "")
        self.check(["", "abc"], "")
        self.check(["กาแฟ", "การ", "กาง"], "กา")


if __name__ == "__main__":
    unittest.main()

Decision table

สถานการณ์	Horizontal shrink	Vertical scan	Min/Max extremes
input เล็กทั่วไป	ดีที่สุดด้าน readability	ดี	กระชับ
mismatch ใกล้ต้น	หยุดเร็ว	หยุดเร็วมาก	ยังต้องหา min/max
memory จำกัด	ดี	ดี	ดีถ้าไม่สร้าง sorted copy
streaming input	ดี เพราะอัปเดต prefix ทีละคำ	ต้องเก็บ/วนทุกคำ	หา min/max streaming ได้ แต่รู้ผลท้าย
input เรียงอยู่แล้ว	ยังใช้ได้	ยังใช้ได้	เทียบหัวท้ายได้ทันที
ห้ามแก้ input	ผ่าน	ผ่าน	ใช้ min/max; อย่า sort in place

Best default: horizontal shrink เพราะอธิบายง่าย รองรับ iterable ทีละคำ และไม่ต้องเรียงข้อมูล; vertical scan เหมาะเมื่ออยากให้จำนวนการเปรียบเทียบเห็นชัด

Edge cases

• list ว่างและคำว่าง
• มีคำเดียว คำตอบคือคำนั้น
• คำหนึ่งเป็น prefix ของอีกคำ
• Unicode ใน Python index เป็น code point ไม่ใช่ grapheme cluster; งาน UI ภาษาเต็มรูปแบบอาจต้อง library แบ่ง grapheme
• case sensitivity ต้องกำหนดก่อน normalize เพราะคำตอบควรอ้างอิงข้อความต้นฉบับหรือ normalized form ให้ชัด

Recap

• Prefix เริ่มที่ตำแหน่งศูนย์เสมอ
• คืนทันทีเมื่อ prefix ว่าง
• horizontal shrink เป็นค่าเริ่มต้นที่อ่านง่าย
• อย่า sort in place หากลำดับ input เป็นของผู้เรียก