0804. 唯一摩尔斯密码词

• 标签：数组、哈希表、字符串
• 难度：简单

题目链接

• 0804. 唯一摩尔斯密码词 - 力扣

题目大意

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

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

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

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

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

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

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

说明：

• $1 \le words.length \le 100$。
• $1 \le words[i].length \le 12$。
• $words[i]$ 由小写英文字母组成。

示例：

• 示例 1：

输入: words = ["gin", "zen", "gig", "msg"]
输出: 2
解释: 
各单词翻译如下:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."

共有 2 种不同翻译, "--...-." 和 "--...--.".

• 示例 2：

输入：words = ["a"]
输出：1

解题思路

思路 1：模拟 + 哈希表

1. 根据题目要求，将所有单词都转换为对应摩斯密码。
2. 使用哈希表存储所有转换后的摩斯密码。
3. 返回哈希表中不同的摩斯密码个数（脊哈希表的长度）作为答案。

思路 1：代码

class Solution:
    def uniqueMorseRepresentations(self, words: List[str]) -> int:
        table = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
        word_set = set()

        for word in words:
            word_mose = ""
            for ch in word:
                word_mose += table[ord(ch) - ord('a')]
            word_set.add(word_mose)

        return len(word_set)

思路 1：复杂度分析

• 时间复杂度：$O(s)$，其中 $s$ 为数组 $words$ 中所有单词的长度之和。
• 空间复杂度：$O(s)$。