ข้อ 5 · LC345 Reverse Vowels of a String 🟢

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

กลับลำดับสระ (a e i o u ทั้งพิมพ์เล็ก/ใหญ่) ในสตริง โดยตัวอักษรอื่นอยู่ที่เดิม

ให้สตริง s มา จงกลับลำดับของสระทุกตัวใน s แล้ว return สตริงที่ได้

การกลับลำดับเฉพาะสระ หมายความว่าสระตัวแรกไปอยู่ตำแหน่งของสระตัวสุดท้าย สระตัวที่สองไปอยู่ตำแหน่งของสระตัวรองสุดท้าย ไล่แบบนี้ไปเรื่อย ๆ

ตัวอักษรที่ไม่ใช่สระต้องอยู่ตำแหน่งเดิมทุกตัว และสระนับรวมทั้ง a e i o u และ A E I O U

Example 1

Input:: s = "IceCreAm"
Output:: "AceCreIm"
Explanation:: สระใน s คือ I, e, e, A ที่ index 0, 2, 5, 6
กลับลำดับตัวสระได้เป็น A, e, e, I แล้ววางกลับลงชุด index เดิม (0, 2, 5, 6)
index 0 จึงกลายเป็น A และ index 6 กลายเป็น I ส่วน c, C, r, m ไม่ขยับเลยสักตัว

Example 2

Input:: s = "leetcode"
Output:: "leotcede"
Explanation:: สระคือ e, e, o, e ที่ index 1, 2, 5, 7
กลับลำดับได้ e, o, e, e — เห็นการเปลี่ยนจริงแค่คู่ index 2 กับ 5 เพราะอีกคู่บังเอิญเป็น e เหมือนกันทั้งคู่

Example 3

Input:: s = "aA"
Output:: "Aa"
Explanation:: สระสองตัวคือ a กับ A สลับกันได้ Aa
ถ้าเช็คสระด้วย "aeiou" อย่างเดียว โปรแกรมจะมองไม่เห็น A แล้วคืนค่า "aA" ซึ่งผิด — เคสนี้คือเคสที่จับคนลืมพิมพ์ใหญ่

Example 4

Input:: s = "xyz"
Output:: "xyz"
Explanation:: ไม่มีสระเลยสักตัว จึงไม่มีอะไรให้สลับ ผลลัพธ์เท่ากับ input เดิม — เคสนี้คือเคสที่ทำโค้ดพังถ้าเขียน loop ไม่รัดกุม (เดี๋ยวจะได้เห็นของจริง)

Constraints (ข้อจำกัด)

1 <= s.length <= 3 × 10^5
s เป็นอักขระ ASCII ที่พิมพ์ได้ (อาจมีตัวเลขหรือเครื่องหมายปนมาด้วย)

⏸ ลองเองก่อน 10 นาที

ข้อนี้มีกับดักที่คนตกกันมากที่สุดเรื่องเดียว และมันซ่อนอยู่ในประโยคสุดท้ายของโจทย์ ลองอ่านโจทย์อีกรอบก่อนเขียน แล้วทดสอบโค้ดตัวเองด้วยคำว่า aA ดู

💡 ใบ้ขั้นที่ 1 — ทำไม reverse ตรง ๆ ใช้ไม่ได้

ถ้ากลับทั้งสตริง ตัวที่ไม่ใช่สระก็ย้ายตำแหน่งไปด้วย ซึ่งผิดกติกา

สิ่งที่ต้องกลับคือ ค่าของสระ เท่านั้น ส่วน ตำแหน่งของสระ ยังเป็นชุดเดิม

💡 ใบ้ขั้นที่ 2 — สองทางที่ทำได้

ทางแรก เก็บตำแหน่งของสระทั้งหมดไว้ในลิสต์ก่อน แล้วจับคู่หัวกับท้ายสลับค่ากัน

ทางที่สอง ใช้ตัวชี้สองตัววิ่งเข้าหากันจากหัวและท้าย ถ้าฝั่งไหนไม่ใช่สระก็ขยับฝั่งนั้นเข้ามา ถ้าเป็นสระทั้งสองฝั่งก็สลับกันแล้วขยับทั้งคู่

💡 ใบ้ขั้นที่ 3 — กับดักที่ทำให้ตกข้อนี้

โจทย์บอกว่าสระนับรวมตัวพิมพ์ใหญ่ด้วย ถ้าเช็คด้วย aeiou อย่างเดียว โปรแกรมจะมองไม่เห็น A E I O U

และ string แก้ผ่านตำแหน่งไม่ได้ จึงต้องแปลงเป็น list ก่อนแล้วค่อย join กลับตอนท้าย

🧭 กล่องสอน — ไล่ตั้งแต่ศูนย์ทีละขั้น (เปิดเมื่อพร้อม)

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

ให้แยกสองอย่างออกจากกันให้ชัด คือ ตำแหน่งที่สระอยู่ กับ ตัวอักษรสระที่อยู่ในตำแหน่งนั้น

โจทย์ให้กลับแค่ ตัวอักษร ส่วน ตำแหน่ง ยังเป็นชุดเดิมทุกตำแหน่ง

ใช้ IceCreAm เป็นตัวอย่าง สระอยู่ตำแหน่ง 0, 2, 5, 6 และตัวอักษรคือ I, e, e, A

กลับลำดับตัวอักษรได้ A, e, e, I แล้ววางกลับลงชุดตำแหน่งเดิม 0, 2, 5, 6 จึงได้ AceCreIm ส่วน c, C, r, m ไม่ขยับเลย

ขั้นที่ 2 · วิธีที่คิดออกก่อน แล้วมันพอไหม

วิธีที่ตรงไปตรงมาที่สุดคือเก็บตำแหน่งสระไว้ก่อน แล้วสลับค่าเป็นคู่ ๆ จากหัวกับท้าย วิธีนี้ถูกต้องและเข้าใจง่าย

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

กติกาของตัวชี้สองตัวมีสามข้อ: ถ้าฝั่งซ้ายไม่ใช่สระให้ขยับซ้ายเข้ามา · ถ้าฝั่งขวาไม่ใช่สระให้ขยับขวาเข้ามา · ถ้าเป็นสระทั้งสองฝั่งให้สลับค่ากันแล้วขยับทั้งคู่

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

โค้ดข้างล่างพิมพ์การตัดสินใจทุกรอบ ให้ดูว่าตัวชี้ขยับตามกติกาสามข้อจริงไหม

ไล่ทีละรอบด้วยตัวชี้สองตัวpython

VOWELS = set("aeiouAEIOU")

def rev(s):
    ch = list(s)
    i, j = 0, len(ch)-1
    while i < j:
        if ch[i] not in VOWELS:
            print(f"  ซ้าย {ch[i]!r} ไม่ใช่สระ -> ขยับ i เป็น {i+1}")
            i += 1
        elif ch[j] not in VOWELS:
            print(f"  ขวา {ch[j]!r} ไม่ใช่สระ -> ขยับ j เป็น {j-1}")
            j -= 1
        else:
            print(f"  สองฝั่งเป็นสระ {ch[i]!r} กับ {ch[j]!r} -> สลับ แล้วขยับทั้งคู่")
            ch[i], ch[j] = ch[j], ch[i]
            i += 1; j -= 1
    return "".join(ch)

print("rev('IceCreAm') =", rev("IceCreAm"))

Output

  ขวา 'm' ไม่ใช่สระ -> ขยับ j เป็น 6
  สองฝั่งเป็นสระ 'I' กับ 'A' -> สลับ แล้วขยับทั้งคู่
  ซ้าย 'c' ไม่ใช่สระ -> ขยับ i เป็น 2
  สองฝั่งเป็นสระ 'e' กับ 'e' -> สลับ แล้วขยับทั้งคู่
  ซ้าย 'C' ไม่ใช่สระ -> ขยับ i เป็น 4
rev('IceCreAm') = AceCreIm

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

และคู่ e กับ e ที่สลับกันในรอบที่สี่ ให้ผลเหมือนไม่ได้สลับ เพราะค่าเท่ากันพอดี ซึ่งไม่ใช่ปัญหาอะไร

ขั้นที่ 4 · กับดักที่ทำให้ตกข้อนี้มากที่สุด

โจทย์เขียนไว้ชัดว่าสระนับรวมตัวพิมพ์ใหญ่ แต่คนส่วนใหญ่เขียนเช็คด้วย aeiou อย่างเดียวโดยไม่รู้ตัว

หลักฐานว่าลืมพิมพ์ใหญ่แล้วผลต่างจริงpython

def wrong(s):
    V = set("aeiou")                  # ลืมพิมพ์ใหญ่
    ch = list(s); i, j = 0, len(ch)-1
    while i < j:
        if ch[i] not in V: i += 1
        elif ch[j] not in V: j -= 1
        else:
            ch[i], ch[j] = ch[j], ch[i]; i += 1; j -= 1
    return "".join(ch)

def right(s):
    V = set("aeiouAEIOU")
    ch = list(s); i, j = 0, len(ch)-1
    while i < j:
        if ch[i] not in V: i += 1
        elif ch[j] not in V: j -= 1
        else:
            ch[i], ch[j] = ch[j], ch[i]; i += 1; j -= 1
    return "".join(ch)

for s in ["IceCreAm", "aA", "leetcode", "xyz"]:
    w, r = wrong(s), right(s)
    mark = "" if w == r else "   <- ต่างกัน!"
    print(f"s={s!r} | ใช้แค่ aeiou -> {w!r} | ใส่พิมพ์ใหญ่ด้วย -> {r!r}{mark}")

Output

s='IceCreAm' | ใช้แค่ aeiou -> 'IceCreAm' | ใส่พิมพ์ใหญ่ด้วย -> 'AceCreIm'   <- ต่างกัน!
s='aA' | ใช้แค่ aeiou -> 'aA' | ใส่พิมพ์ใหญ่ด้วย -> 'Aa'   <- ต่างกัน!
s='leetcode' | ใช้แค่ aeiou -> 'leotcede' | ใส่พิมพ์ใหญ่ด้วย -> 'leotcede'
s='xyz' | ใช้แค่ aeiou -> 'xyz' | ใส่พิมพ์ใหญ่ด้วย -> 'xyz'

สองบรรทัดท้ายให้ผลตรงกัน ซึ่งเป็นเหตุผลที่บั๊กนี้รอดการเทสต์ได้ง่าย ถ้าเทสต์แต่คำที่มีแต่พิมพ์เล็กก็จะไม่เห็นอะไรผิด

เคสสั้นที่สุดที่จับบั๊กนี้ได้

คำว่า aA ยาวแค่สองตัวอักษร แต่จับบั๊กเรื่องพิมพ์ใหญ่ได้ทันที เวลาเขียนโจทย์แนวจำแนกตัวอักษร ให้หาเคสสั้นสุดที่แยกถูกกับผิดออกจากกันแบบนี้เสมอ

ขั้นที่ 5 · ทำไมต้องแปลงเป็น list ก่อน

โค้ดเริ่มด้วย ch = list(s) เพราะ string แก้ผ่านตำแหน่งไม่ได้ ถ้าเขียน s[i] = s[j] ตรง ๆ จะขึ้น TypeError

เมื่อเป็น list แล้วจึงสลับค่าได้ในบรรทัดเดียวด้วย ch[i], ch[j] = ch[j], ch[i] แล้วปิดท้ายด้วย join เพื่อคืนเป็น string ตามที่โจทย์ขอ

ต้นทุนของท่านี้คือหน่วยความจำ O(n) เพิ่มขึ้นหนึ่งเท่า ซึ่งเลี่ยงไม่ได้ในภาษาที่ string แก้ไม่ได้

🔓 เฉลยเต็ม พร้อมอธิบายทีละบรรทัด (ลองเองก่อนนะ)พับไว้ด้านใน — คลิกเมื่อพร้อมดู

คำตอบpython

class Solution:
    def reverseVowels(self, s: str) -> str:
        VOWELS = set("aeiouAEIOU")     # ใส่พิมพ์ใหญ่ด้วย ไม่งั้นตกข้อนี้
        ch = list(s)                   # string แก้ผ่านตำแหน่งไม่ได้ จึงต้องแปลงเป็น list
        i, j = 0, len(ch) - 1

        while i < j:
            if ch[i] not in VOWELS:
                i += 1                 # ซ้ายไม่ใช่สระ ขยับซ้ายเข้ามา
            elif ch[j] not in VOWELS:
                j -= 1                 # ขวาไม่ใช่สระ ขยับขวาเข้ามา
            else:
                ch[i], ch[j] = ch[j], ch[i]   # สระทั้งสองฝั่ง สลับกัน
                i += 1
                j -= 1

        return "".join(ch)

อ่านโค้ดทีละส่วน

เก็บสระไว้ใน set เพราะการเช็คสมาชิกใน set เร็วกว่าใน string หรือ list
list(s) แปลงเป็นลิสต์เพื่อให้แก้ค่าตามตำแหน่งได้
เงื่อนไข while i < j ทำให้หยุดพอตัวชี้มาเจอกัน ถ้าใช้ <= จะสลับตัวเองกับตัวเองโดยไม่จำเป็น
ลำดับ if elif else สำคัญ ต้องขยับฝั่งที่ไม่ใช่สระให้หมดก่อน จึงจะสลับได้ถูกคู่
join คืนค่าเป็น string ตามที่โจทย์ขอ

ต้นทุน

เวลา O(n) เพราะตัวชี้สองตัวเดินเข้าหากันรวมกันไม่เกิน n ก้าว · หน่วยความจำ O(n) จากลิสต์ที่แปลงมา

เช็คลิสต์ก่อนกดส่ง

ชุดสระมีทั้งพิมพ์เล็กและพิมพ์ใหญ่ครบสิบตัว
ทดสอบด้วย aA ต้องได้ Aa
ทดสอบสตริงที่ไม่มีสระเลย เช่น xyz ต้องคืนค่าเดิมและไม่ติดลูปไม่จบ
ใช้ i < j ไม่ใช่ i <= j
คืนค่าเป็น string ไม่ใช่ list