Giả sử ta có một danh sách các từ, mỗi từ có thể được viết thành chuỗi nối của mã Morse của từng chữ cái. Ví dụ, từ "cba" có thể viết thành "-.-..--...", đây là nối của "-.-." | "-..." | ".-"). Loại nối này được gọi là biến đổi của một từ.
Ta biết Mã Morse Quốc tế định nghĩa mã hóa chuẩn nơi mỗi chữ cái được ánh xạ thành một chuỗi chấm và gạch, như sau: "a" ánh xạ thành ".-", "b" thành "-...", "c" thành "-.-.", v.v.
Dưới đây là danh sách 26 chữ cái tiếng Anh:
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
Ví dụ, nếu đầu vào là ["gin", "zen", "gig", "msg"], thì đầu ra sẽ là 2, vì biến đổi của mỗi từ là: "gin" thành "--...-.", "zen" thành "--...-.", "gig" thành "--...--." và "msg" thành "--...--.".
Để giải quyết, ta thực hiện các bước sau:
- morse_codes := [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
- s := một tập hợp (set) mới
- Với mỗi word trong words, thực hiện:
- temp := chuỗi rỗng
- Với mỗi c trong word, thực hiện:
- temp := temp + morse_codes[ASCII của c - 97]
- Thêm temp vào s
- Trả về kích thước của s
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
class Solution: def uniqueMorseRepresentations(self, words): morse_codes=[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."] s=set() for word in words: temp='' for c in word: temp+=morse_codes[ord(c)-97] s.add(temp) return len(s) ob = Solution() print(ob.uniqueMorseRepresentations(["gin", "zen", "gig", "msg"]))
Đầu vào
["gin", "zen", "gig", "msg"]
Đầu ra
2