[LeetCode]804. Unique Morse Code Words

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：
字数统计：482 字 | 阅读时长：2 分钟

804. 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:

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

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.

1
2
3
4
5
6
7
8
9
10
11
Example:
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 "--...--.".

Note:

  • 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.

大概解释一下题目：摩斯码，26个小写字母各对应一串密码串，不同的英文单词可能出现同样的摩斯码；

输入：一个数组，数组中包含多个单词；

输出：单词转换成摩斯码后，总的摩斯编码类别有几种；

解题思路：

  1. 要得到不同的摩斯码，就是不能有重复的，就可以用集合(set)来存储转换后的摩斯码；
  2. 26个小写字母对应的摩斯码是固定的，就用数组直接初始化；
  3. 字母a对应的ASCII码为97，数组第一个元素的索引index为0，直接减去97即可得到对应的摩斯码编码；
  4. 循环遍历vector中的word，循环遍历word中的每一个字母；

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int uniqueMorseRepresentations(vector<string>& words) {
        string morse[26] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        set<string> morse_set;
        string str_morse;
        for (string &word : words) {
            unsigned len = word.length();
            for(unsigned i = 0; i < len; ++i) {
                unsigned index  = (unsigned)(word[i]-97);
                str_morse.append(morse[index]);
            }
            morse_set.insert(str_morse);
            str_morse.clear();
        }
        return morse_set.size();
    }
};

result

Runtime: 4 ms, faster than 100.00% of C++ online submissions for Unique Morse Code Words.
Memory Usage: 8.7 MB, less than 100.00% of C++ online submissions for Unique Morse Code Words.