Đề bài
Trình soạn thảo văn bản gạch chân những từ mà nó không biết. Hãy nạp từ điển vào một tập hợp (set, cài đặt bằng bảng băm) để mỗi lần tra cứu đều nhanh, rồi duyệt qua văn bản.
Một từ là một dãy dài nhất có thể gồm các chữ cái tiếng Anh (A-Z, a-z) và dấu nháy đơn (apostrophe); mọi ký tự khác (dấu cách, chữ số, dấu câu) đều phân tách các từ. Khi so sánh không phân biệt chữ hoa chữ thường, nên The khớp với mục the trong từ điển.
Hãy viết spell_checker(dictionary, text).
Đầu vào
dictionary: Các từ đã biết, có thể viết hoa hay thường tùy ý.
text: Văn bản cần kiểm tra.
Đầu ra
Trả về các từ sai chính tả ở dạng chữ thường, theo thứ tự xuất hiện lần đầu trong văn bản, mỗi từ chỉ liệt kê một lần. Nếu mọi từ đều có trong từ điển, trả về danh sách rỗng.
Ràng buộc
0 ≤ kích thước từ điển ≤ 2,000
0 ≤ độ dài text ≤ 10,000
Ví dụ
Đầu vào:
dictionary = ["the", "cat", "sat", "on", "mat"]
text = "The cat sat on teh mat, the cta!"
Kết quả mong đợi:
expected = ["teh", "cta"]
Đầu vào:
std::vector<std::string> dictionary = {"the", "cat", "sat", "on", "mat"};
std::string text = "The cat sat on teh mat, the cta!";
Kết quả mong đợi:
std::vector<std::string> expected = {"teh", "cta"};
Đầu vào:
string[] dictionary = new string[] {"the", "cat", "sat", "on", "mat"};
string text = "The cat sat on teh mat, the cta!";
Kết quả mong đợi:
string[] expected = new string[] {"teh", "cta"};
Giải thích
teh và cta không có trong từ điển. Với các từ còn lại, chữ hoa thường và dấu phẩy không ảnh hưởng gì: ["teh", "cta"].
Đầu vào:
dictionary = ["Don't", "stop"]
text = "don't STOP, dont stop dont"
Kết quả mong đợi:
expected = ["dont"]
Đầu vào:
std::vector<std::string> dictionary = {"Don't", "stop"};
std::string text = "don't STOP, dont stop dont";
Kết quả mong đợi:
std::vector<std::string> expected = {"dont"};
Đầu vào:
string[] dictionary = new string[] {"Don't", "stop"};
string text = "don't STOP, dont stop dont";
Kết quả mong đợi:
string[] expected = new string[] {"dont"};
Giải thích
don't giữ nguyên dấu nháy và khớp với từ điển; dont là từ lạ và chỉ được liệt kê một lần: ["dont"].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Đổi các từ trong từ điển sang chữ thường một lần khi tạo tập hợp.
Gợi ý 2
Ghép từ hiện tại từng ký tự một, và kết thúc từ khi gặp một ký tự không phải chữ cái cũng không phải dấu nháy đơn.
Gợi ý 3
Giữ thêm một tập hợp thứ hai chứa các từ đã báo.
Độ phức tạp mong đợi
thời gian O(D + T), bộ nhớ phụ O(D + T)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.