唯一摩尔斯密码词

难度: Easy

国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串，比如:

'a' 对应 ".-" ，
'b' 对应 "-..." ，
'c' 对应 "-.-." ，以此类推。

为了方便，所有 26 个英文字母的摩尔斯密码表如下：

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

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

例如，"cab" 可以写成 "-.-..--..." ，(即 "-.-." + ".-" + "-..." 字符串的结合)。我们将这样一个连接过程称作 单词翻译 。

对 words 中所有单词进行单词翻译，返回不同 单词翻译 的数量。

示例 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] 由小写英文字母组成

Submission

运行时间: 20 ms

内存: 16.6 MB

mapper = {'a': '.-', 'b': '-...', 'c': '-.-.', 'd': '-..', 'e': '.',
          'f': '..-.', 'g': '--.', 'h': '....', 'i': '..', 'j': '.---',
          'k': '-.-', 'l': '.-..', 'm': '--', 'n': '-.', 'o': '---',
          'p': '.--.', 'q': '--.-', 'r': '.-.', 's': '...', 't': '-',
          'u': '..-', 'v': '...-', 'w': '.--', 'x': '-..-', 'y': '-.--', 'z': '--..'}

class Solution:
    def uniqueMorseRepresentations(self, words: List[str]) -> int:
        return len(set(''.join(mapper[ch] for ch in word) for word in words))

Explain

该题解首先定义了一个摩尔斯密码的映射表mapper，将每个英文字母映射到对应的摩尔斯密码。然后在uniqueMorseRepresentations函数中，使用列表推导式遍历输入的单词数组words，对每个单词中的每个字母使用mapper进行转换，将转换后的摩尔斯密码拼接成一个字符串。最后，使用set()函数去除重复的摩尔斯密码字符串，并返回其长度，即不同单词翻译的数量。

时间复杂度: O(nm)

空间复杂度: O(n)

mapper = {'a': '.-', 'b': '-...', 'c': '-.-.', 'd': '-..', 'e': '.',
          'f': '..-.', 'g': '--.', 'h': '....', 'i': '..', 'j': '.---',
          'k': '-.-', 'l': '.-..', 'm': '--', 'n': '-.', 'o': '---',
          'p': '.--.', 'q': '--.-', 'r': '.-.', 's': '...', 't': '-',
          'u': '..-', 'v': '...-', 'w': '.--', 'x': '-..-', 'y': '-.--', 'z': '--..'}

class Solution:
    def uniqueMorseRepresentations(self, words: List[str]) -> int:
        # 使用集合去重并计算不同摩尔斯密码字符串的数量
        return len(set(''.join(mapper[ch] for ch in word) for word in words))

Explore

在Python中，`mapper`是一个字典（dictionary），它允许通过键（这里是英文字母）来快速访问和检索值（这里是对应的摩尔斯密码）。字典在Python中是通过哈希表实现的，因此提供了平均时间复杂度为O(1)的快速访问。这种数据结构的使用确保了从英文字母到摩尔斯密码的映射既快速又高效。

集合（set）是一个无序的数据结构，它内部使用哈希表来存储元素，这使得其添加、删除和查找操作的平均时间复杂度都是O(1)。使用集合可以有效地去除重复项，并且在检查是否已存在某个元素时比列表更高效，因为列表的这些操作的时间复杂度为O(n)。虽然字典也具有类似的性能特点，但集合更适合本场景因为我们只关心元素的存在与否，而不需要键值对的映射关系。

一种可能的优化是预先计算并存储所有可能的摩尔斯密码转换，特别是如果我们需要多次调用`uniqueMorseRepresentations`函数的话。这样，对于每个单词的转换操作就变成了查找操作，可能会进一步提高效率。另外，如果输入的单词数组非常大，使用生成器表达式而不是列表推导式可以节省内存，因为生成器表达式不会一次性将所有项加载到内存中。