Đề bài
Trong một trò chơi đoán từ trên lớp, một người giấu một từ, người kia đoán những từ có cùng độ dài. Sau mỗi lượt đoán, trò chơi hiện một gợi ý gồm một ký tự cho mỗi vị trí:
- chính chữ cái đó nếu từ đoán có đúng chữ cái ở đúng vị trí;
+nếu chữ cái có trong từ bí mật nhưng ở vị trí khác;*nếu chữ cái không có trong từ bí mật.
Chữ cái lặp lại được xử lý bằng cách đếm. Trước hết, đánh dấu mọi chữ khớp đúng vị trí. Những chữ cái của từ bí mật chưa được khớp đúng vị trí sẽ được dùng cho dấu +. Duyệt từ đoán từ trái sang phải, mỗi chữ không khớp đúng vị trí sẽ lấy một bản còn lại của chữ cái đó và nhận dấu +; khi không còn bản nào thì nhận dấu *.
Hãy viết hidden_word_clue(hidden, guess).
Đầu vào
hidden: Từ bí mật, viết hoa.
guess: Từ đoán, viết hoa, cùng độ dài với hidden.
Đầu ra
Trả về gợi ý dưới dạng chuỗi có cùng độ dài với hai từ.
Ràng buộc
1 ≤ độ dài từ ≤ 20
Cả hai từ chỉ gồm A-Z
Ví dụ
Đầu vào:
hidden = "PLANT"
guess = "PANEL"
Kết quả mong đợi:
expected = "P++*+"
Đầu vào:
std::string hidden = "PLANT";
std::string guess = "PANEL";
Kết quả mong đợi:
std::string expected = "P++*+";
Đầu vào:
string hidden = "PLANT";
string guess = "PANEL";
Kết quả mong đợi:
string expected = "P++*+";
Giải thích
P đúng vị trí. A, N và L có trong PLANT nhưng ở chỗ khác, còn E thì không có: P++*+.
Đầu vào:
hidden = "APPLE"
guess = "PAPPY"
Kết quả mong đợi:
expected = "++P**"
Đầu vào:
std::string hidden = "APPLE";
std::string guess = "PAPPY";
Kết quả mong đợi:
std::string expected = "++P**";
Đầu vào:
string hidden = "APPLE";
string guess = "PAPPY";
Kết quả mong đợi:
string expected = "++P**";
Giải thích
Chữ P ở giữa (vị trí 3) đúng vị trí. APPLE còn dư một chữ P, nên chữ P đầu tiên nhận +, còn chữ P thừa thứ hai nhận *. A ở chỗ khác, Y không có: ++P**.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Duyệt hai lượt: lượt đầu đánh dấu các chữ đúng vị trí, lượt sau xử lý phần còn lại.
Gợi ý 2
Đếm các chữ cái của từ bí mật chưa được khớp đúng vị trí.
Gợi ý 3
Mỗi dấu `+` dùng hết một bản của chữ cái đó trong bảng đếm.
Độ phức tạp mong đợi
thời gian O(n), bộ nhớ phụ O(1)
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.