ข้อ 1 · LC1768 Merge Strings Alternately 🟢

ขั้นที่ 1 · โจทย์นี้ขออะไรจริง ๆ

แปลโจทย์เป็นภาพก่อน ให้นึกภาพคนสองแถวยืนรอเข้าประตูเดียวกัน แถวซ้ายคือ word1 แถวขวาคือ word2

ประตูปล่อยคนทีละคน สลับแถวไปเรื่อย ๆ ซ้าย ขวา ซ้าย ขวา ลำดับที่คนเดินออกมาคือคำตอบ

กติกาที่ต้องอ่านให้แตกคือประโยคสุดท้าย: สองแถวอาจยาวไม่เท่ากัน พอแถวหนึ่งหมดคน คนที่เหลือของอีกแถวต้องเดินออกรวดเดียวจนหมด ไม่ต้องรอสลับกับใครอีก

สังเกตว่ากติกาไม่สนใจว่าแถวไหนยาวกว่า สนใจแค่ว่าแถวไหนหมดก่อน

ขั้นที่ 2 · ลองทำด้วยมือก่อนเขียนโค้ด

หยิบเคส word1 = ab กับ word2 = pqrs มาไล่ด้วยมือ

รอบแรกหยิบ a แล้ว p ได้ ap · รอบสองหยิบ b แล้ว q ได้ apbq · ถึงตรงนี้แถวซ้ายหมดแล้ว เหลือ r กับ s ในแถวขวา

r กับ s จึงต่อท้ายติดกันเป็น apbqrs ไม่ได้แทรกสลับกับอะไรอีก เพราะไม่มีใครให้สลับด้วยแล้ว

ขั้นที่ 3 · วิธีแรกที่คนส่วนใหญ่คิดออก แล้วมันพอไหม

วิธีแรกที่คิดออกมักเป็น วนตามความยาวของตัวที่สั้นกว่า แล้วหยิบสลับกัน ซึ่งถูกครึ่งเดียว

ลองดูว่าถ้าหยุดแค่นั้นจะเกิดอะไรขึ้น

def wrong(word1, word2):
    res = []
    i = j = 0
    while i < len(word1) and j < len(word2):
        res.append(word1[i]); res.append(word2[j])
        i += 1; j += 1
    return "".join(res)          # ลืมต่อส่วนที่เหลือ

def right(word1, word2):
    res = []
    i = j = 0
    while i < len(word1) and j < len(word2):
        res.append(word1[i]); res.append(word2[j])
        i += 1; j += 1
    return "".join(res) + word1[i:] + word2[j:]

for a, b in [("abc","pqr"), ("ab","pqrs"), ("abcd","pq")]:
    w, r = wrong(a,b), right(a,b)
    print(f"a={a!r} b={b!r} | ลืมเก็บเศษ -> {w!r} | ถูก -> {r!r} | ตรงกันไหม: {w==r}")

a='abc' b='pqr' | ลืมเก็บเศษ -> 'apbqcr' | ถูก -> 'apbqcr' | ตรงกันไหม: True
a='ab' b='pqrs' | ลืมเก็บเศษ -> 'apbq' | ถูก -> 'apbqrs' | ตรงกันไหม: False
a='abcd' b='pq' | ลืมเก็บเศษ -> 'apbq' | ถูก -> 'apbqcd' | ตรงกันไหม: False

สังเกตบรรทัดแรก: เคสที่ยาวเท่ากันให้ผลตรงกันทั้งสองวิธี นี่คือสาเหตุที่หลายคนเทสต์ด้วยเคสแรกแล้วคิดว่าโค้ดถูกแล้ว

แต่พอสองฝั่งยาวไม่เท่ากัน คำตอบขาดท้ายไปเลย และไม่มี error ขึ้นให้เห็น

ขั้นที่ 4 · กุญแจที่ปลดล็อกข้อนี้

กุญแจอยู่ที่การใช้ตัวชี้สองตัวคือ i กับ j แล้วปล่อยให้มันค้างค่าไว้หลังลูปจบ

เพราะเงื่อนไข while ใช้คำว่า and ลูปจะหยุดทันทีที่ฝั่งใดฝั่งหนึ่งหมด ตอนนั้น i กับ j ชี้อยู่ที่ตำแหน่งแรกที่ยังไม่ได้หยิบพอดี

เราจึงเขียน word1[i:] + word2[j:] ต่อท้ายได้เลย โดยไม่ต้องเขียน if เช็คว่าใครหมดก่อน เพราะฝั่งที่หมดแล้ว slice จะให้สตริงว่างซึ่งบวกเข้าไปก็ไม่เปลี่ยนอะไร

ขั้นที่ 5 · เดินตามโค้ดทีละสเต็ป

โค้ดข้างล่างพิมพ์สถานะทุกรอบให้ดู ให้ดูค่า i กับ j ตอนลูปจบเป็นพิเศษ เพราะมันคือหัวใจของข้อนี้

def merge(word1, word2):
    res = []
    i = j = 0
    while i < len(word1) and j < len(word2):
        res.append(word1[i]); res.append(word2[j])
        print(f"  i={i} j={j} -> หยิบ {word1[i]!r} แล้ว {word2[j]!r} | ได้ {''.join(res)!r}")
        i += 1; j += 1
    print(f"  ลูปจบ: i={i} j={j} | เหลือ word1[{i}:]={word1[i:]!r} word2[{j}:]={word2[j:]!r}")
    return "".join(res) + word1[i:] + word2[j:]

print("merge('ab','pqrs') =", merge("ab", "pqrs"))

  i=0 j=0 -> หยิบ 'a' แล้ว 'p' | ได้ 'ap'
  i=1 j=1 -> หยิบ 'b' แล้ว 'q' | ได้ 'apbq'
  ลูปจบ: i=2 j=2 | เหลือ word1[2:]='' word2[2:]='rs'
merge('ab','pqrs') = apbqrs

บรรทัดสุดท้ายก่อนคำตอบคือจุดสำคัญ: word1[2:] ได้สตริงว่างเพราะหมดแล้ว ส่วน word2[2:] ได้ rs ซึ่งคือเศษที่ต้องเอาไปต่อท้าย

ขั้นที่ 6 · ทำไมต้อง join ไม่ใช่ +=

สังเกตว่าโค้ดเก็บตัวอักษรลง list ชื่อ res แล้วค่อย join ตอนท้าย ไม่ได้เขียน res += word1[i] ไปเรื่อย ๆ

เหตุผลคือเรื่องเดียวกับส่วนที่ 4 ของหน้าแนวคิด: string แก้ในที่เดิมไม่ได้ การต่อ string ทีละตัวในลูปจึงเป็นการสร้างสตริงใหม่ทุกรอบ

ข้อนี้ n แค่ 100 จะเขียนแบบไหนก็ผ่าน แต่การฝึกท่าที่ถูกตั้งแต่ข้อง่ายจะช่วยเราตอนเจอข้อที่ n เป็นแสน