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 <= 201 <= words.length <= 50words[i].length == pattern.lengthpatternvàwords[i]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:
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ẫupatternhay 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[i] trong từ, ta tìm chỉ số xuất hiện đầu tiên của word[i] trong từ word và chỉ số xuất hiện đầu tiên của pattern[i] 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.
4. Code chạy bằng cơm
Function chính không nói làm gì rồi, tại vì chỉ cần hàm isMatch trả về true thì ta thêm vào danh sách kết quả.
Chúng ta sẽ đi xem hàm isMatch này hoạt động như thế nào với ví dụ 1:
Ta có chuỗi đầu tiên trong words là "abc", ta kiểm tra với chuỗi pattern:
Đầu tiên ta có chỉ mục của ký tự 'a' đầu tiên của cả hai chuỗi đều là 0:
Tiếp theo chỉ mục của ký tự 'b' đầu tiên cũng đều là 1, ok mọi việc vẫn đang suôn sẻ:
Cuối cùng, chỉ mục thứ 2 của chuỗi pattern là ký tự 'b', mà chỉ mục đầu tiên của ký tự 'b' trong chuỗi này là 1; trong khi đó ký tự thứ 2 của chuỗi word lại là 'c', chỉ mục không giống nhau vậy nên ta trả về false:
Hãy thử với word = "mee":
Ta có chỉ mục của ký tự 'a' đầu tiên trong chuỗi pattern là bằng 0; chỉ mục của ký tự 'm' đầu tiên trong chuỗi word là bằng 0, chúng bằng nhau nên ta sẽ tới chữ cái tiếp theo:
Tiếp theo, chỉ mục của ký tự 'b' đầu tiên trong chuỗi pattern là bằng 1; chỉ mục của ký tự 'e' đầu tiên trong chuỗi word là bằng 1, chúng bằng nhau nên ta sẽ tới chữ cái tiếp theo:
Cuối cùng, ở chuỗi pattern, ta có ký tự cuối cùng là 'b', hàm sẽ tìm index của ký tự 'b' đầu tiên (ở đây chính là bằng 1); tương tự như vậy với ký tự 'e' của chuỗi word. Cả hai giá trị index này đều bằng 1. Vậy nên kết quả trả về true:
5. Code bằng máy
Code Golang của chúng ta như sau:
func findAndReplacePattern(words []string, pattern string) []string {
res := []string{}
for _, word := range words {
if isMath(word, pattern) {
res = append(res, word)
}
}
return res
}
func isMath(word string, pattern string) bool {
for i := 0; i < len(word); i++ {
x := strings.Index(word, string(word[i]))
y := strings.Index(pattern, string(pattern[i]))
if x != y {
return false
}
}
return true
}
6. Kết thúc
Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!
Bình luận