ข้อ 6 · LC151 Reverse Words in a String 🟡

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

กลับลำดับคำในประโยค และยุบช่องว่างส่วนเกินให้เหลือช่องว่างเดียวคั่นระหว่างคำ

ให้สตริง s ที่เป็นประโยคซึ่งมีคำหลายคำคั่นด้วยช่องว่าง จง return สตริงใหม่ที่กลับลำดับคำ

กลับแค่ลำดับของคำเท่านั้น ตัวอักษรในแต่ละคำยังสะกดเหมือนเดิม

s อาจมีช่องว่างนำหน้า มีช่องว่างต่อท้าย หรือมีช่องว่างซ้อนกันหลายช่องระหว่างคำ แต่ผลลัพธ์ต้องคั่นคำด้วยช่องว่างเพียงหนึ่งช่อง และไม่มีช่องว่างเหลือที่หัวหรือท้าย

Example 1

Input:: s = "the sky is blue"
Output:: "blue is sky the"
Explanation:: input สะอาดอยู่แล้ว (คั่นช่องเดียว ไม่มีช่องว่างหัวท้าย) จึงเหลืองานเดียวคือสลับลำดับคำ 4 คำ: คำสุดท้าย blue ต้องมาอยู่หน้าสุด แล้วไล่ย้อนมาจนถึง the ที่ไปอยู่ท้ายสุด

Example 2

Input:: s = " hello world "
Output:: "world hello"
Explanation:: มีช่องว่าง 2 ช่องนำหน้าและ 2 ช่องต่อท้าย ซึ่งไม่ใช่ส่วนหนึ่งของคำไหนเลย จึงต้องหายไปทั้งหมด
เหลือคำจริงแค่ 2 คำคือ hello กับ world สลับกันได้ world hello โดยผลลัพธ์ยาว 11 ตัวอักษร ไม่ใช่ 15 เท่า input

Example 3

Input:: s = "a good example"
Output:: "example good a"
Explanation:: ระหว่าง good กับ example มีช่องว่าง 3 ช่อง แต่ช่องว่างกี่ช่องก็ยังหมายถึง "รอยต่อระหว่างคำ" อันเดียวกัน จึงต้องยุบเหลือช่องเดียวในผลลัพธ์
นี่คือเคสที่หักคอวิธีที่ใช้ช่องว่างหนึ่งตัวเป็นตัวคั่นแบบตรงตัว

Constraints (ข้อจำกัด)

1 <= s.length <= 10^4
s ประกอบด้วยตัวอักษรอังกฤษ (พิมพ์เล็ก/ใหญ่), ตัวเลข และช่องว่าง
รับประกันว่ามีคำอย่างน้อยหนึ่งคำใน s

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

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

💡 ใบ้ขั้นที่ 1 — แยกงานออกเป็นสามชิ้น

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

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

💡 ใบ้ขั้นที่ 2 — split สองแบบไม่เหมือนกัน

s.split() ที่ไม่ใส่อะไรในวงเล็บ กับ s.split(" ") ที่ใส่ช่องว่าง ให้ผลต่างกันมาก

ลองรันสองแบบเทียบกันกับประโยคที่มีช่องว่างซ้อนหลายช่อง แล้วจะเห็นความต่างทันที

💡 ใบ้ขั้นที่ 3 — คำตอบเกือบครบ

python

return " ".join(reversed(s.___()))     # เลือก split แบบไหน

หรือใช้ s.split()[::-1] แทน reversed(...) ก็ได้ผลเหมือนกัน

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

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

อ่านให้ชัดก่อนว่าโจทย์ให้กลับลำดับ คำ ไม่ใช่กลับ ตัวอักษร ถ้าเผลอกลับตัวอักษรจะได้คำที่สะกดกลับหลังซึ่งผิด

และงานจริงของข้อนี้ไม่ได้อยู่ที่การกลับลำดับ ซึ่งง่ายมาก แต่อยู่ที่การจัดการช่องว่างให้สะอาด

โจทย์บอกว่า input อาจสกปรกได้สามแบบ คือมีช่องว่างนำหน้า มีช่องว่างต่อท้าย และมีช่องว่างซ้อนหลายช่องระหว่างคำ แต่ output ต้องสะอาดเสมอ

ขั้นที่ 2 · เครื่องมือที่ Python เตรียมไว้ให้แล้ว

หลายคนพอเห็นเรื่องช่องว่างก็เริ่มคิดจะเขียนลูปนับช่องว่างเอง ซึ่งยาวและพลาดง่าย ทั้งที่ Python จัดการให้แล้ว

split ที่ไม่ใส่อะไรในวงเล็บ ทำงานสามอย่างให้ฟรีpython

s = "  a good   example  "
print("s =", repr(s))
words = s.split()
print("s.split()          ->", words, " (ยุบช่องว่างซ้ำ + ตัดหัวท้ายให้เอง)")
print('s.split(" ")       ->', s.split(" "), " <- มีสตริงว่างโผล่มาเต็มเลย")
print("reversed แล้ว join ->", repr(" ".join(reversed(words))))

Output

s = '  a good   example  '
s.split()          -> ['a', 'good', 'example']  (ยุบช่องว่างซ้ำ + ตัดหัวท้ายให้เอง)
s.split(" ")       -> ['', '', 'a', 'good', '', '', 'example', '', '']  <- มีสตริงว่างโผล่มาเต็มเลย
reversed แล้ว join -> 'example good a'

บรรทัดที่สองคือหัวใจของข้อนี้ s.split() ทำสามอย่างพร้อมกัน คือแยกคำ ยุบช่องว่างที่ติดกัน และตัดช่องว่างหัวท้ายทิ้ง

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

ขั้นที่ 3 · เลือกผิดตัวแล้วเกิดอะไรขึ้น

ถ้าใช้ split ผิดแบบ แล้ว join กลับตรง ๆ ช่องว่างที่เกินจะติดมาในคำตอบ

เทียบผลของ split สองแบบpython

def wrong(s):
    return " ".join(reversed(s.split(" ")))

def right(s):
    return " ".join(reversed(s.split()))

for s in ["the sky is blue", "  hello world  ", "a good   example"]:
    print(f"s={s!r}")
    print(f"   split(' ') -> {wrong(s)!r}")
    print(f"   split()    -> {right(s)!r}   <- ถูก")

Output

s='the sky is blue'
   split(' ') -> 'blue is sky the'
   split()    -> 'blue is sky the'   <- ถูก
s='  hello world  '
   split(' ') -> '  world hello  '
   split()    -> 'world hello'   <- ถูก
s='a good   example'
   split(' ') -> 'example   good a'
   split()    -> 'example good a'   <- ถูก

เคสแรกให้ผลตรงกัน เพราะ input สะอาดอยู่แล้ว นี่คือกับดักที่ทำให้คนคิดว่าโค้ดถูก

เคสที่สองช่องว่างหัวท้ายติดมาด้วย และเคสที่สามช่องว่างสามช่องกลางประโยคยังอยู่ครบ ทั้งสองเคสจึงตอบผิด

บทเรียนที่กว้างกว่าข้อนี้

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

ขั้นที่ 4 · สามวิธีเขียนที่ให้ผลเหมือนกัน

พอรู้ว่าใช้ s.split() แล้ว การกลับลำดับเขียนได้หลายแบบ เลือกแบบที่อ่านสบายที่สุด

สามแบบ ได้ผลเดียวกันpython

" ".join(reversed(s.split()))    # อ่านง่ายที่สุด บอกเจตนาชัด
" ".join(s.split()[::-1])       # ใช้ slice กลับด้าน สั้นกว่าเล็กน้อย
" ".join(s.split()[::-1])       # เหมือนบรรทัดบน เขียนติดกันได้เลยในบรรทัดเดียว

ข้อต่างเล็ก ๆ คือ reversed() ไม่สร้างลิสต์ใหม่ แต่ [::-1] สร้าง ในข้อนี้ n เล็กจนไม่ต่างกันในทางปฏิบัติ

ขั้นที่ 5 · คำถามต่อยอดที่มักถูกถาม

โจทย์ต้นฉบับมีคำถามแถมว่า ถ้าภาษาที่ใช้มี string ที่แก้ในที่เดิมได้ จะทำให้ใช้หน่วยความจำเพิ่มเป็น O(1) ได้ไหม

คำตอบคือได้ วิธีคลาสสิกมีสามขั้น คือกลับตัวอักษรทั้งสตริงก่อน แล้วกลับตัวอักษรในแต่ละคำอีกที แล้วจัดการช่องว่างส่วนเกินในที่เดิม

แต่ Python ทำไม่ได้ เพราะ string เป็น immutable ตามที่เรียนในส่วนที่ 1 ของหน้าแนวคิด ถ้าโดนถามในสัมภาษณ์ ให้ตอบว่ารู้วิธีแต่ภาษานี้ทำไม่ได้ พร้อมอธิบายเหตุผล

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

คำตอบpython

class Solution:
    def reverseWords(self, s: str) -> str:
        # s.split() ไม่ใส่ argument = แยกด้วย whitespace ใดก็ได้
        #   ยุบช่องว่างที่ติดกันหลายช่องให้เหลือรอยต่อเดียว และตัดช่องว่างหัวท้ายให้เอง
        # reversed(...) กลับลำดับคำ (ไม่ใช่กลับตัวอักษรในคำ)
        # " ".join(...) ประกอบกลับ โดยคั่นด้วยช่องว่างหนึ่งช่องพอดี
        return " ".join(reversed(s.split()))

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

s.split() ให้ลิสต์ของคำที่สะอาดแล้ว ไม่มีสตริงว่างปน ไม่ต้องเขียน strip() เพิ่ม
reversed(...) กลับลำดับสมาชิกในลิสต์ ซึ่งคือกลับลำดับคำตามที่โจทย์ขอ
join ประกอบกลับด้วยตัวคั่นหนึ่งช่อง ซึ่งตรงกับข้อกำหนดของ output พอดี
ใช้ join ไม่ใช่ += ในลูป ตามหลักที่เรียนในส่วนที่ 4 ของหน้าแนวคิด

ต้นทุน

เวลา O(n) เพราะ split, reversed และ join ทำงานตามความยาวของ s · หน่วยความจำ O(n) จากลิสต์คำและสตริงผลลัพธ์

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

ใช้ s.split() ไม่ใช่ s.split(" ")
ทดสอบด้วยประโยคที่มีช่องว่างนำหน้าและต่อท้าย
ทดสอบด้วยประโยคที่มีช่องว่างซ้อนหลายช่องระหว่างคำ
ตรวจว่าคำแต่ละคำยังสะกดเหมือนเดิม ไม่ได้กลับตัวอักษรในคำ