Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/unique-morse-code-words/
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
Mã Morse quốc tế định nghĩa quy chuẩn mã hóa trong đó mỗi chữ cái được ánh xạ tới một loạt các dấu chấm và dấu gạch ngang, như sau:
'a'ánh xạ tới".-"'b'ánh xạ tới"-..."'c'ánh xạ tới"-.-.", và cứ thế đến hết.
Và dưới đây là mã Morse của 26 chữ cái tiếng Anh:
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
Cho một mảng chuỗi words, trong đó mỗi từ trong mảng có thể viết dưới dạng mã Morse.
Ví dụ: "cab" có thể được viết là "-.-..--...", là từ ghép của "-.-.", ".-", và "-...". Chúng ta sẽ gọi sự kết nối như vậy là sự biến đổi của một từ.
Trả về số lượng biến đổi khác nhau trong mảng chuỗi words.
Điều kiện:
1 <= words.length <= 100.1 <= words[i].length <= 12.words[i]bao gồm các chữ cái tiếng Anh viết thường.
Bài toán minh họa 1:
Input: words = ["gin","zen","gig","msg"]
Output: 2
Explanation: The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."
There are 2 different transformations: "--...-." and "--...--.".
Bài toán minh họa 2:
Input: words = ["a"]
Output: 1
3. Phân tích
Ố kề. Một dạng bài mã hóa, khá là thú vị đúng không ạ? Bài này cũng không quá phức tạp đâu, chúng ta cùng phân tích nhé!
Họ cho chúng ta một mảng chuỗi words chứa các từ, bây giờ chúng ta cần phải chuyển các từ đó sang dạng mã Morse, sau khi chuyển xong rồi thì đếm xem có bao nhiêu mã khác biệt không trùng lặp. Vậy thì ta có hai công việc chính cần làm:
Đầu tiên là chuyển các từ chứa chữ cái tiếng Anh sang dạng mã Morse, cách làm thì chúng ta sẽ chuyển từng chữ cái một, sau đó dùng StringBuilder để nối các mã lại với nhau:
Nếu các bạn quan tâm, có thể tham khảo thêm bài viết của mình về StringBuilder tại đây!Cuối cùng, sau khi đã có hết tất cả các mã Morse, ta sẽ đếm xem có bao nhiêu mã khác biệt, không trùng lặp. Nhắc đến khác biệt, không trùng lặp, tôi nghĩ ngay đến cấu trúc dữ liệu
HashSet. Yep, chúng ta sẽ nhét hết tất cả mã Morse vàoHashSet, sau đó chỉ việc trả vềsize()củaHashSetlà xong.
Done! Đến bước tiếp theo thôi!
4. Code bằng cơm
Công việc đầu tiên chúng ta cần làm là mã hóa các chữ cái của từ có trong mảng words sang mã Morse, vậy thì làm hẳn một cái function chuyên làm việc này đi. Ok, tham số đưa vào function này sẽ là mỗi word trong mảng words ở trên, chúng ta sẽ chuyển word này sang về dạng mảng các chữ cái wordCh bằng cách dùng method toCharArray(), cùng với đó là tạo mới một đối tượng StringBuilder:
Trong function này chúng ta cũng cần có một mảng chuỗi chứa các mã Morse, copy luôn từ đề bài cho đúng thứ tự:
String[] morse = { ".-", "-...", "-.-.", "-..", ".", "..-.",
"--.", "....", "..", ".---","-.-", ".-..", "--", "-.", "---",
".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-",
"-.--", "--.." };
Giờ đến phần quan trọng của function này nè, chúng ta sẽ làm một vòng lặp for qua mảng wordCh ở trên, gặp kí tự nào, ta thay thế kí tự đó ở đúng vị trí đó trong mảng chuỗi morse kia:
Ây khoan, cái đoạn sb.append(morse[w - 'a']) kia là sao ạ?
Để mình giải thích một chút. Từ trong ra ngoài, w - 'a' nghĩa là sao? Trong bảng mã ASCII, kí tự 'a' có giá trị là 97 (dưới dạng hệ thập phân). Và khi chúng ta lấy mỗi chữ cái có trong wordCh trừ đi 'a', vô hình chung ta sẽ có được số thứ tự của chính chữ cái w đó, ví dụ: c - a = 99 - 97 = 2, nhìn vào mảng morse ta sẽ thấy tại vị trí index = 2, ta thấy chính là mã Morse của chữ c.
Vậy morse[w - 'a'] chính là việc ta lấy mã Morse của chữ cái có vị trí index tại w - 'a'. Còn method append() thì dùng để nối các chữ cái lại với nhau thôi.
Tiếp theo chúng ta sẽ cần một HashSet để chứa các mã Morse vừa được chuyển:
Cuối cùng, chúng ta chỉ cần trả về kích thước của HashSet là xong.
5. Code thôi chờ gì nữa
Về cơ bản, code của chúng ta sẽ như sau:
public static int uniqueMorseRepresentations(String[] words) {
Set<String> set = new HashSet<>();
for (String w : words) {
set.add(getStringMorse(w));
}
return set.size();
}
public static String getStringMorse(String word) {
char[] wordCh = word.toCharArray();
StringBuilder sb = new StringBuilder();
String[] morse = { ".-", "-...", "-.-.", "-..", ".", "..-.",
"--.", "....", "..", ".---","-.-", ".-..", "--", "-.", "---",
".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-",
"-.--", "--.." };
for (char w : wordCh) {
sb.append(morse[w - 'a']);
}
return sb.toString();
}
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