Cùng giải leetcode! Bài 2325. Decode the Message

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/decode-the-message/

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

Cho hai chuỗi key và message tương ứng với khóa để giải mã và mật thư. Cách để giải mật thư message như sau:

• Sử dụng 26 chữ cái tiếng Anh viết thường xuất hiện đầu tiên, không trùng lặp trong key làm thứ tự cho bảng giải mã.
• Căn chỉnh bảng giải mã với bảng chữ cái tiếng Anh thông thường.
• Mỗi chữ cái trong mật thư message được thay thế bằng cách sử dụng bảng giải mã.
• vị trí khoảng trắng ' ' không thay đổi.
  Ví dụ: cho key = "happy boy", các chữ cái xuất hiện ở trong key là: h, a, p, y, b, o. Gióng với thứ tự của bảng chữ cái tiếng Anh ta có thể quy đổi thành: 'h' -> 'a', 'a' -> 'b', 'p' -> 'c', 'y' -> 'd', 'b' -> 'e', 'o' -> 'f'.

Trả về kết quả là mật thư đã được giải mã.

Điều kiện:

• 26 <= key.length <= 2000
• key bao gồm các chữ cái tiếng Anh viết thường và khoảng trắng ' '.
• Mọi chữ cái tiếng Anh trong key phải xuất hiện ít nhất một lần.
• 1 <= message.length <= 2000.
• message bao gồm các chữ cái tiếng Anh viết thường và khoảng trắng ' '.

Bài toán minh họa 1:

Input: key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv"
Output: "this is a secret"
Explanation: The diagram above shows the substitution table.
It is obtained by taking the first appearance of each letter in "the quick brown fox jumps over the lazy dog".

Bài toán minh họa 2:

Input: key = "eljuxhpwnyrdgtqkviszcfmabo", message = "zwx hnfx lqantp mnoeius ycgk vcnjrdb"
Output: "the five boxing wizards jump quickly"
Explanation: The diagram above shows the substitution table.
It is obtained by taking the first appearance of each letter in "eljuxhpwnyrdgtqkviszcfmabo".

3. Phân tích

Mới đọc qua thấy bài này hơi phức tạp một chút, nhưng không sao, nếu chúng ta bóc tách, chia nhỏ vấn đề lớn thành nhỏ, mọi chuyện sẽ rõ ràng hơn. Mục đích của chúng ta là phải giải mã được mật thư, nhưng muốn giải mã được mật thư, ta phải dựa vào chuỗi mật mã key, đối chiếu các chữ cái chỉ xuất hiện một lần trong key với bảng chữ cái tiếng Anh. Cuối cùng, ta thay các chữ cái trong mật thư message dựa vào những chữ cái đã được đối chiếu từ bảng giả mã. Hai công việc chính mà chúng ta cần làm sẽ là:

• Đầu tiên người ta sẽ cho mình chuỗi mật mã key, nó có thể là một câu rất dài (như bài toán minh họa 1), hoặc chỉ là một đoạn các chữ cái sắp xếp ko theo trình tự nào (như bài toán minh họa 2). Chính vì điều kiện các chữ cái trong key khi đưa vào bảng giải mã chỉ được xuất hiện một lần duy nhất khiến tôi nghĩ ngay đến kiểu cấu trúc dữ liệu HashSet để giải quyết, tuy nhiên chúng ta lại phải đối chiếu các chữ cái của key với bảng chữ cái tiếng Anh theo thứ tự thông thường, như vậy chúng ta nên làm bảng giải mã theo kiểu key - value, vậy thì kiểu cấu trúc dữ liệu HashMap sẽ hợp lý hơn nhiều.
• Dựa vào bảng giải mã sử dụng HashMap, chúng ta đối chiếu các chữ cái trong message với bảng giải mã để ra được nội dung của mật thư.

Cũng không quá khó phải không ạ?

4. Code chạy bằng cơm

Bước đầu tiên, chúng ta cần phải xóa tất cả khoảng trắng (nếu có) ở trong key đi, chỉ để xuất hiện các chữ cái mà thôi, và ta sẽ sử dụng method replace() làm công việc này:

Tiếp theo chúng ta cần một bảng giải mã HashMap có tên map với key là các chữ cái xuất hiện một lần duy nhất trong key và value là các chữ cái trong bảng chữ cái tiếng anh theo thứ tự thông thường:

Vì bảng chữ cái tiếng Anh theo thứ tự thông thường luôn bắt đầu bằng chữ 'a' và kết thúc bằng chữ 'z', nên ta có thể làm một vòng lặp while để thêm value vào trong map, điều kiện dừng là khi nào đến chữ cái 'z' thì thôi. Tại sao lại nhỏ hơn 'z'? Dựa vào bảng mã ASCII, chữ cái 'a' sẽ tương ứng với số 97 trong hệ thập phân, vậy là khi ch + 1, máy tính sẽ hiểu là chữ cái tiếp theo trong bảng chữ cái:

Ta cần có con trỏ index để chạy từ đầu đến cuối chuỗi key đã bỏ khoảng trắng đã làm ở trên, kí tự ch thì cứ mỗi khi thêm thành công một cặp key - value trong map sẽ cộng thêm 1 để tới chữ cái tiếp theo:

Như key = "the quick brown fox jumps over the lazy dog", ta bỏ khoảng trắng thì sẽ thành key = "thequickbrownfoxjumpsoverthelazydog". Nếu chữ cái chưa từng xuất hiện thì ta sẽ thêm vào map, nhưng khi con trỏ index chạy đến chữ o thứ hai trong từ fox, nó phát hiện chữ o đã xuất hiện một lần rồi, khi ấy con trỏ ch vẫn đứng yên, còn index sẽ tiến thêm một bước. Sau khi tiến thêm một bước, chữ x chưa từng xuất hiện, vậy ta sẽ gán nó vào bảng giải mã tương ứng với chữ o trong bảng chữ cái tiếng Anh:

Vậy là chúng ta đã có bảng giải mã, tiếp theo chúng ta sẽ giải mã mật thư message dựa bảng vừa làm được. Trong function này, chúng ta sẽ biến chuỗi message thành mảng các chữ cái arr để dễ quy đổi. Và thêm một đối tượng StringBuilder tên sb để hứng kết quả:

Chúng ta sẽ cần một vòng lặp for để duyệt từ đầu tới cuối mảng arr:

Và cứ khi nào ta gặp kí tự trùng với kí tự trong bảng giải mã, ta sẽ đối chiếu nó và thay bằng kí tự trong bảng chữ cái tiếng anh vào sb, nếu là khoảng trắng thì ta thêm khoảng trắng vào:

Thế là xong! Triển bước tiếp theo nào!

5. Code thôi nào các bạn

Code của chúng ta sẽ như sau:

 public static String decodeMessage(String key, String message) {
     HashMap<Character, Character> map = getCodeTable(key);

     return decodeMes(map, message);
 }


// Function làm nhiệm vụ tạo bảng giải mã
 public static HashMap getCodeTable(String key) {
     HashMap<Character, Character> map = new HashMap<>();
     char ch = 'a';
     int index = 0;
     key = key.replace(" ", "");

     while (ch <= 'z') {
         if (!map.containsKey(key.charAt(index))) {
             map.put(key.charAt(index), ch);
             index++;
             ch++;
         } else {
             index++;
         }
     }

     return map;
 }

// Function làm nhiệm vụ giải mã mật thư
 public static String decodeMes(HashMap map, String message) {
     StringBuilder sb = new StringBuilder();

     char[] arr = message.toCharArray();

     for (int i = 0; i < arr.length; i++) {
         if (map.containsKey(arr[i])) {
             sb.append(map.get(arr[i]));
         } else {
             sb.append(" ");
         }
     }

     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!!!