Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Kiểm tra chính tả

Liệt kê các từ trong văn bản không có trong từ điển, không phân biệt hoa thường và bỏ qua dấu câu.

Bạn sẽ học được gì

  • Nạp các từ vào tập hợp để tra cứu nhanh
  • Tách văn bản thành từ theo quy tắc ký tự
  • Báo cáo kết quả theo thứ tự gặp lần đầu, không trùng lặp

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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"].

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.