Easy

题目描述

国际摩尔斯密码定义了一种标准编码，其中每个字母映射为一系列点和划，如下所示：

'a' 映射为 ".-",
'b' 映射为 "-...",
'c' 映射为 "-.-.", 等等。

为了方便，下面给出了英文字母表中 26 个字母的完整表：

[".-","-…","-.-.","-..",".","..-.","–.","….","..",".—","-.-",".-..","–","-.","—",".–.","–.-",".-.","…","-","..-","…-",".–","-..-","-.–","–.."]

给你一个字符串数组 words，每个单词可以写成每个字母对应摩尔斯密码的连接。

例如，"cab" 可以写成 "-.-..--..."，这是 "-.-."、".-" 和 "-..." 字符串的连接。我们将这样一个连接过程称为单词翻译。

在所有给定单词中，返回不同单词翻译的数量。

示例 1：

输入：words = [“gin”,“zen”,“gig”,“msg”] 输出：2 解释： 每个单词的翻译如下: “gin” -> “–…-.” “zen” -> “–…-.” “gig” -> “–…–.” “msg” -> “–…–.”

共有 2 种不同的翻译，"–…-." 和 “–…–.”.

示例 2：

输入：words = [“a”] 输出：1

提示：

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 12
  • words[i] 由小写英文字母组成

解题思路

这道题要求统计不同的摩尔斯密码翻译数量。核心思路是将每个单词转换为摩尔斯密码，然后用集合（Set）去重统计。

解题步骤：

  1. 建立字母到摩尔斯密码的映射表
  2. 遍历每个单词，将单词中的每个字母转换为对应的摩尔斯密码并连接
  3. 将转换结果存入集合中自动去重
  4. 返回集合的大小即为不同翻译的数量

时间复杂度分析：

  • 需要遍历所有单词：O(n)
  • 对于每个单词，需要遍历其所有字符：O(m)
  • 总体时间复杂度：O(n×m)，其中 n 是单词数量，m 是单词的平均长度

空间复杂度分析：

  • 需要存储摩尔斯密码映射表：O(1)（固定26个字母）
  • 需要集合存储不同的翻译：最坏情况 O(n)
  • 总体空间复杂度：O(n)

这是一个典型的哈希表应用问题，利用集合的去重特性可以很优雅地解决。

代码实现

class Solution {
public:
    int uniqueMorseRepresentations(vector<string>& words) {
        vector<string> morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        
        unordered_set<string> transformations;
        
        for (const string& word : words) {
            string morseCode = "";
            for (char c : word) {
                morseCode += morse[c - 'a'];
            }
            transformations.insert(morseCode);
        }
        
        return transformations.size();
    }
};

class Solution:
    def uniqueMorseRepresentations(self, words: List[str]) -> int:
        morse = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
        
        transformations = set()
        
        for word in words:
            morse_code = ""
            for char in word:
                morse_code += morse[ord(char) - ord('a')]
            transformations.add(morse_code)
        
        return len(transformations)

public class Solution {
    public int UniqueMorseRepresentations(string[] words) {
        string[] morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        
        HashSet<string> transformations = new HashSet<string>();
        
        foreach (string word in words) {
            StringBuilder morseCode = new StringBuilder();
            foreach (char c in word) {
                morseCode.Append(morse[c - 'a']);
            }
            transformations.Add(morseCode.ToString());
        }
        
        return transformations.Count;
    }
}

/**
 * @param {string[]} words
 * @return {number}
 */
var uniqueMorseRepresentations = function(words) {
    const morse = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."];
    
    const transformations = new Set();
    
    for (const word of words) {
        let morseCode = "";
        for (const char of word) {
            morseCode += morse[char.charCodeAt(0) - 'a'.charCodeAt(0)];
        }
        transformations.add(morseCode);
    }
    
    return transformations.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n×m)n为单词数量，m为单词平均长度
空间复杂度O(n)最坏情况下需要存储n个不同的翻译