Tiếp nỗi chuỗi series “Mỗi ngày 1 thuật toán” là bài toán tìm hai chuỗi cùng có các ký tự giống nhau. Để giải bài toán này, CodeGym sẽ hướng dẫn bạn ý tưởng thuật toán để giải. Đồng thời, cung cấp ba đoạn mã nguồn quan trọng, bao gồm: Java, PHP và Python cho đề bài này.
Đề bài: Cho hai chuỗi string1 và string2. Hãy kiểm tra xem string1 và string2 có cùng chứa các ký tự giống như nhau hay không? (trật tự của các ký tự có thể khác nhau, không phân biệt chữ hoa và chữa thường)
1. Thuật toán:
Ý tưởng chính của thuật toán này là sử dụng bảng băm để lưu trữ tần suất xuất hiện của mỗi ký tự, sau đó đối chiếu với chuỗi ký tự thứ hai để kiểm tra xem chúng có chứa cùng những ký tự đó hay không.
- Loại bỏ khoảng trắng và chuyển hai chuỗi ký tự sang chữ thường để so sánh không phân biệt chữ hoa chữ thường.
- Kiểm tra xem hai chuỗi ký tự có cùng độ dài không. Nếu không, chúng không thể là anagram nên trả về kết quả false.
- Tạo ra một bảng băm (dictionary) để lưu trữ tần suất xuất hiện của mỗi ký tự trong chuỗi ký tự thứ nhất.
- Duyệt qua chuỗi ký tự thứ nhất, tăng giá trị tương ứng với mỗi ký tự trong bảng băm.
- Duyệt qua chuỗi ký tự thứ hai, giảm giá trị tương ứng với mỗi ký tự trong bảng băm. Nếu gặp ký tự không có trong bảng băm, trả về kết quả false vì chúng không thể là anagram.
- Kiểm tra tất cả các giá trị trong bảng băm có bằng 0 không. Nếu có, trả về kết quả true vì chúng là anagram. Nếu không, trả về kết quả false.
Đó ý tưởng giải quyết bài toán bài toán tìm hai chuỗi cùng có các ký tự giống nhau. Dưới đây sẽ là ví dụ cụ thể mã nguồn trong từng ngôn ngữ lập trình.
2. Pseudo-code
3. Mã nguồn Java:
4. Mã nguồn PHP:
5. Mã nguồn Python:
Theo bạn thì thuật toán này có độ phức tạp là bao nhiêu? Đây chỉ mới là một cách, bạn có thêm ý tưởng nào để giải bài toán này nữa không? Hãy để lại câu trả lời của mình nhé. Hy vọng bài viết trên sẽ hữu ích với bạn.
Để cập nhật chuỗi bài viết “Mỗi ngày một thuật toán” của CodeGym, hãy theo dõi Tại đây nhé!!!
0 Lời bình