โจทย์ทั้งหมด
ง่าย 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

ตัวตัดคำและคลังคำศัพท์

แยกข้อความเป็นคำตัวพิมพ์เล็กและสร้างคลังคำศัพท์ที่เรียงตามความถี่ ซึ่งเป็นขั้นแรกของโมเดลภาษาทุกตัว

สิ่งที่คุณจะได้เรียนรู้

  • แยกข้อความเป็น token คำตัวพิมพ์เล็ก
  • นับความถี่ของคำ
  • เรียงคลังคำศัพท์ตามความถี่แล้วตามตัวอักษร

โจทย์

โมเดลภาษาทำงานกับ token ไม่ใช่ข้อความดิบ ตัวตัดคำอย่างง่ายจะแปลงข้อความเป็นตัวพิมพ์เล็ก และถือว่าทุกลำดับของตัวอักษร a-z และตัวเลข 0-9 คือหนึ่งคำ ส่วนอื่นทั้งหมด (ช่องว่าง เครื่องหมายวรรคตอน อักขระอื่น) เป็นตัวคั่นคำ

สร้าง คลังคำศัพท์: คำที่ไม่ซ้ำกัน เรียงตามความถี่ (มากที่สุดก่อน) ถ้าเท่ากันให้เรียงตามตัวอักษร ตำแหน่งของคำในรายการนี้คือ ID ของ token

จง implement build_vocabulary(text)

อินพุต

text: ข้อความใด ๆ

เอาต์พุต

คืนค่าคลังคำศัพท์เป็นรายการคำ ถ้าข้อความไม่มีคำเลย ให้คืนรายการว่าง

เงื่อนไข

0 ≤ ความยาวของ text ≤ 100,000

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
text = "The cat sat on the mat. The end!"

ผลลัพธ์ที่คาดหวัง:
expected = ["the", "cat", "end", "mat", "on", "sat"]
อินพุต:
std::string text = "The cat sat on the mat. The end!";

ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"the", "cat", "end", "mat", "on", "sat"};
อินพุต:
string text = "The cat sat on the mat. The end!";

ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"the", "cat", "end", "mat", "on", "sat"};

คำอธิบาย

เมื่อเป็นตัวพิมพ์เล็ก คำต่าง ๆ คือ the, cat, sat, on, the, mat, the, end โดย "the" ปรากฏ 3 ครั้ง คำอื่นปรากฏคำละครั้งและเรียงตามตัวอักษร: ["the", "cat", "end", "mat", "on", "sat"]

ตัวอย่างที่ 2
อินพุต:
text = "AI, ai and A.I. (2024)"

ผลลัพธ์ที่คาดหวัง:
expected = ["ai", "2024", "a", "and", "i"]
อินพุต:
std::string text = "AI, ai and A.I. (2024)";

ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"ai", "2024", "a", "and", "i"};
อินพุต:
string text = "AI, ai and A.I. (2024)";

ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"ai", "2024", "a", "and", "i"};

คำอธิบาย

คำ: ai, ai, and, a, i, 2024 โดย "ai" ปรากฏสองครั้ง คำอื่นปรากฏคำละครั้ง เรียงตามตัวอักษรโดยตัวเลขมาก่อนตัวอักษร: ["ai", "2024", "a", "and", "i"]

แนวทางการแก้

ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ

คำใบ้ 1

ดึงเฉพาะช่วงที่เป็นตัวอักษรและตัวเลข แปลงเป็นตัวพิมพ์เล็ก และ ignore อักขระอื่นทั้งหมด

คำใบ้ 2

นับความถี่ของแต่ละคำ แล้วเรียงตามความถี่จากมากไปน้อย และเรียงตามตัวอักษรถ้าเท่ากัน

คำใบ้ 3

ถ้า text ไม่มีคำที่ใช้ได้ ให้คืนค่าเป็น empty list ไม่ใช่ singleton หรือ null

ความซับซ้อนที่คาดหวัง

เวลา O(n log k), หน่วยความจำเพิ่ม O(k)

แหล่งอ้างอิง

โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

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

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก