網頁

▼

2018/12/11

LeetCode Unique Morse Code Words 唯一的摩斯密碼

本篇為LeetCode上演算法的簡單問題，Unique Morse Code Words。

題目如下：

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: "a" maps to ".-", "b" maps to "-...", "c" maps to "-.-.", and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-"
,".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--",
"-..-","-.--","--.."]

Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, "cba" can be written as "-.-..--...", (which is the concatenation "-.-." + "-..." + ".-"). We'll call such a concatenation, the transformation of a word.

Return the number of different transformations among all words we have.

Example 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 "--...--.".

Notes:

  • The length of words will be at most 100.
  • Each words[i] will have length in range [1, 12].
  • words[i] will only consist of lowercase letters.

摩斯密碼定義一套標準的編碼，每一個英文字母對照著一組由點(dot)'.'和線(dash)'-'組合成的符號，例如字母"a"對照的是".-"，"b"對照的是"-..."，"c"對照的是"-.-."。

全部的字母定義如上方區塊中的陣列。

輸入參數為多個文字組成的列表，列表中每個文字的字母可轉成摩斯密碼轉成的符號，例如"cba"可轉譯成"-.-..--..."（由"-.-." + "-..." + ".-"串接成）。

計算每個文字所轉譯的摩斯密碼串接符號共有幾組不同。

Notes:

  • 文字列表的個數不超過100個字。
  • 每個文字的字數為1到12。
  • 每個文字皆為小寫英文字母。

解法的基本步驟為：

  1. 迴圈文字列表。
  2. 將每個文字轉成字符陣列並迴圈
  3. 將每個字符依照ASCII表的規則扣除97（直接減'a'也可），即為摩斯密碼陣列中該字母所對映的符號索引。
  4. 從摩斯密碼陣列表中取出該字母對映的密碼，並串接成字串。
  5. 將字串放入Set中確保唯一。
  6. 計算Set中元素的數量並回傳。
public static int uniqueMorseRepresentations(String[] words) {
    String[] codes = { ".-", "-...", "-.-.", "-..", ".", "..-.",
            "--.", "....", "..", ".---", "-.-", ".-..", "--",
            "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-",
            "...-", ".--", "-..-", "-.--", "--.." };
    Set<String> set = new HashSet<>();
    for (String word : words) {
        StringBuilder sb = new StringBuilder(12);
        for(char c : word.toCharArray()) {
            sb.append(codes[(c - 97)]); // 或codes[(c - 'a')]
        }
        set.add(sb.toString());
    }
    return set.size();
}

在以StringBuilder串接符號時，依題目條件可以先宣告好空間(capacity)為12。（StringBuilder預設空間長度為16，）



參考：

沒有留言:

張貼留言