Find and Replace Pattern bằng Golang

[hovanban]

1. Mở đầu

Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.

2. Đề bài
Link bài tập: Find and Replace Pattern

Cho một danh sách các chuỗi words và một chuỗi pattern, bạn cần trả về danh sách các chuỗi trong words mà khớp với pattern. Bạn có thể trả kết quả theo bất kỳ thứ tự nào.

Một chuỗi khớp với mẫu nếu tồn tại một hoán vị của các chữ cái p sao cho sau khi thay thế mỗi chữ cái x trong mẫu bằng p(x), chúng ta có được từ mong muốn.

Lưu ý rằng một hoán vị của các chữ cái là một ánh xạ đối xứng từ các chữ cái này sang các chữ cái khác: mỗi chữ cái được ánh xạ vào một chữ cái khác, và không có hai chữ cái nào ánh xạ vào cùng một chữ cái.

Ví dụ 1:

Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Giải thích: "mee" khớp với mẫu vì có một hoán vị {a -> m, b -> e, ...}.
"ccc" không khớp với mẫu vì {a -> c, b -> c, ...} không phải là một hoán vị, vì a và b ánh xạ vào cùng một chữ cái.

Ví dụ 2:

Input: words = ["a","b","c"], pattern = "a"
Output: ["a","b","c"]

Ràng buộc:

• 1 <= độ dài của pattern <= 20
• 1 <= words.length <= 50
• words.length == pattern.length
  [*]pattern và words là các chữ cái tiếng Anh thường.

3. Phân tích
3.1. Ý tưởng

Để giải quyết bài toán này, bạn có thể sử dụng một vòng lặp để kiểm tra từng từ trong danh sách words. Dựa trên quy tắc rằng một từ phải khớp với mẫu pattern, bạn có thể thực hiện các bước sau:

1. • Khởi tạo một mảng kết quả res để lưu trữ các từ khớp với mẫu.
   • Lặp qua từng từ trong danh sách words.
   • Đối với mỗi từ, gọi hàm isMath để kiểm tra xem nó khớp với mẫu pattern hay không. Nếu khớp, thêm từ đó vào danh sách kết quả res.

Kết quả cuối cùng sẽ chứa danh sách các từ khớp với mẫu pattern.

3.2. Gợi ý

Hàm isMatch làm những gì?

Hàm isMath thực hiện kiểm tra khớp giữa word và pattern.

Trong vòng lặp, với mỗi chữ cái word trong từ, ta tìm chỉ số xuất hiện đầu tiên của word trong từ word và chỉ số xuất hiện đầu tiên của pattern trong mẫu pattern.

Nếu chỉ số x không bằng chỉ số y, tức là các chữ cái này không ánh xạ đến nhau, chúng ta trả về false, đánh dấu từ này không khớp với mẫu.

Nếu qua tất cả các ký tự và không có sự không khớp nào xảy ra, ta trả về true, đánh dấu từ này khớp với mẫu.

CÔNG TY TNHH TƯ VẤN TRUYỀN THÔNG MINARA
ĐỊA CHỈ:
- 182 Trần Bình Trọng, P.3, Q.5, Tp.HCM
- 27 Đường số 16, Trung Tâm Hành Chính Dĩ An, Bình Dương.
Điện thoại: 097.777.1060
Email: info@minara.vn
Website: www.minara.vn