Giả sử có danh sách từ và một mẫu, ta phải tìm từ nào trong danh sách khớp với mẫu. Một từ khớp mẫu nếu tồn tại hoán vị chữ cái p sao cho sau khi thay mỗi chữ x trong mẫu bằng p(x), ta được từ mục tiêu. Ta phải trả về danh sách từ khớp mẫu.
Ví dụ, đầu vào ["abc","deq","mee","aqq","dkd","ccc"] và mẫu "abb", kết quả ["mee", "aqq"]. Ở đây mee và aqq khớp kiểu mẫu "abb". Nhưng "ccc" không khớp vì không phải hoán vị.
Để giải quyết, ta làm theo các bước −
- định nghĩa phương thức convert(word). Nó hoạt động như −
- counter := 1, s := chuỗi rỗng
- s := s + chuỗi counter
- với i từ 1 đến len(word)-1
- j := i - 1
- khi j >= 0
- nếu word[j] == word[i], break
- giảm j 1
- nếu j > -1, s := s + s[j], ngược lại tăng counter 1 và s := s + counter dạng chuỗi
- trả về s
- phương thức chính:
- tạo mảng word_num rỗng, mảng res rỗng
- với mỗi i trong words
- thêm convert(i) vào word_num
- pattern := convert(pattern)
- với i từ 0 đến len(words)-1
- nếu words_num[i] == pattern, thêm words[i] vào res
- trả về res
Xem triển khai sau −
Ví dụ
class Solution(object): def findAndReplacePattern(self, words, pattern): words_num = [] result = [] for i in words: words_num.append(self.convert(i)) pattern = self.convert(pattern) for i in range(len(words)): if words_num[i] == pattern: result.append(words[i]) return result def convert(self,word): counter = 1 s = "" s+=str(counter) for i in range(1,len(word)): j= i -1 while j>=0: if word[j] == word[i]: break j-=1 if j >-1: s+=s[j] else: counter+=1 s+=str(counter) return s ob = Solution() print(ob.findAndReplacePattern(["abc","deq","mee","aqq","dkd","ccc"],"abb"))
Đầu vào
["abc","deq","mee","aqq","dkd","ccc"] "abb"
Kết quả
['mee', 'aqq']