โจทย์
โปรแกรมพิมพ์เอกสารจะขีดเส้นใต้คำที่มันไม่รู้จัก ให้โหลดพจนานุกรมลงในเซต (ตารางแฮช) เพื่อให้การค้นหาแต่ละครั้งรวดเร็ว แล้วจึงไล่อ่านข้อความ
คำหนึ่งคำคือกลุ่มของตัวอักษรภาษาอังกฤษ (A-Z, a-z) และเครื่องหมายอะพอสทรอฟีที่ต่อกันยาวที่สุด อักขระอื่นทั้งหมด (ช่องว่าง ตัวเลข เครื่องหมายวรรคตอน) ถือเป็นตัวคั่นคำ การเปรียบเทียบคำไม่สนใจตัวพิมพ์เล็กใหญ่ ดังนั้น The ตรงกับคำ the ในพจนานุกรม
จงเขียน spell_checker(dictionary, text)
อินพุต
dictionary: คำที่รู้จัก อาจเป็นตัวพิมพ์เล็กหรือใหญ่ก็ได้
text: ข้อความที่ต้องการตรวจ
เอาต์พุต
คืนค่าคำที่สะกดผิดเป็นตัวพิมพ์เล็ก เรียงตามลำดับที่ปรากฏครั้งแรกในข้อความ และแต่ละคำแสดงเพียงครั้งเดียว ถ้ารู้จักทุกคำ ให้คืนค่าลิสต์ว่าง
เงื่อนไข
0 ≤ ขนาดของพจนานุกรม ≤ 2,000
0 ≤ ความยาวของ text ≤ 10,000
ตัวอย่าง
อินพุต:
dictionary = ["the", "cat", "sat", "on", "mat"]
text = "The cat sat on teh mat, the cta!"
ผลลัพธ์ที่คาดหวัง:
expected = ["teh", "cta"]
อินพุต:
std::vector<std::string> dictionary = {"the", "cat", "sat", "on", "mat"};
std::string text = "The cat sat on teh mat, the cta!";
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"teh", "cta"};
อินพุต:
string[] dictionary = new string[] {"the", "cat", "sat", "on", "mat"};
string text = "The cat sat on teh mat, the cta!";
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"teh", "cta"};
คำอธิบาย
teh และ cta ไม่อยู่ในพจนานุกรม ส่วนคำอื่น ๆ ตัวพิมพ์เล็กใหญ่และจุลภาคไม่มีผล ได้ ["teh", "cta"]
อินพุต:
dictionary = ["Don't", "stop"]
text = "don't STOP, dont stop dont"
ผลลัพธ์ที่คาดหวัง:
expected = ["dont"]
อินพุต:
std::vector<std::string> dictionary = {"Don't", "stop"};
std::string text = "don't STOP, dont stop dont";
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"dont"};
อินพุต:
string[] dictionary = new string[] {"Don't", "stop"};
string text = "don't STOP, dont stop dont";
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"dont"};
คำอธิบาย
don't ยังมีอะพอสทรอฟีอยู่และตรงกับพจนานุกรม ส่วน dont ไม่รู้จักและแสดงเพียงครั้งเดียว ได้ ["dont"]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
แปลงคำในพจนานุกรมเป็นตัวพิมพ์เล็กครั้งเดียวตอนสร้างเซต
คำใบ้ 2
สร้างคำปัจจุบันทีละอักขระ และจบคำเมื่อเจออักขระที่ไม่ใช่ตัวอักษรและไม่ใช่อะพอสทรอฟี
คำใบ้ 3
เก็บเซตที่สองไว้สำหรับคำที่รายงานไปแล้ว
ความซับซ้อนที่คาดหวัง
เวลา O(D + T), หน่วยความจำเพิ่ม O(D + T)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน