Đề bài
Trong một trò chơi chữ, người chơi nhập một danh sách từ và một chữ cái, trò chơi chỉ hiển thị những từ có dùng chữ cái đó. Chữ hoa và chữ thường được coi là một, nên K khớp với kite và k khớp với Kansas.
Hãy viết contains_character(words, letter).
Đầu vào
words: Danh sách các từ.
letter: Một chữ cái tiếng Anh.
Đầu ra
Trả về các từ có chứa chữ cái đó, giữ nguyên thứ tự và cách viết ban đầu. Từ nào lặp lại thì giữ đúng số lần xuất hiện. Nếu không có từ nào khớp, trả về danh sách rỗng.
Ràng buộc
0 ≤ độ dài words ≤ 1000
Mỗi từ có từ 1 đến 30 chữ cái ASCII
letter là một chữ cái ASCII
Ví dụ
Đầu vào:
words = ["apple", "Berry", "kiwi", "Grape"]
letter = "r"
Kết quả mong đợi:
expected = ["Berry", "Grape"]
Đầu vào:
std::vector<std::string> words = {"apple", "Berry", "kiwi", "Grape"};
std::string letter = "r";
Kết quả mong đợi:
std::vector<std::string> expected = {"Berry", "Grape"};
Đầu vào:
string[] words = new string[] {"apple", "Berry", "kiwi", "Grape"};
string letter = "r";
Kết quả mong đợi:
string[] expected = new string[] {"Berry", "Grape"};
Giải thích
Berry và Grape có chữ r; apple và kiwi thì không.
Đầu vào:
words = ["Ohio", "Utah", "Iowa"]
letter = "O"
Kết quả mong đợi:
expected = ["Ohio", "Iowa"]
Đầu vào:
std::vector<std::string> words = {"Ohio", "Utah", "Iowa"};
std::string letter = "O";
Kết quả mong đợi:
std::vector<std::string> expected = {"Ohio", "Iowa"};
Đầu vào:
string[] words = new string[] {"Ohio", "Utah", "Iowa"};
string letter = "O";
Kết quả mong đợi:
string[] expected = new string[] {"Ohio", "Iowa"};
Giải thích
Không phân biệt hoa thường, nên cả Ohio lẫn Iowa đều khớp.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Đưa cả từ lẫn chữ cái về cùng dạng chữ hoa hoặc chữ thường trước khi so sánh.
Gợi ý 2
Trả về từ gốc, không phải bản sao đã đổi dạng chữ.
Gợi ý 3
Đừng loại bỏ các từ trùng; chỉ cần kiểm tra từng từ một cách độc lập.
Độ phức tạp mong đợi
thời gian O(total letters), bộ nhớ phụ O(n)
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.