What is the time complexity of the solution for Unique Morse Code Words?

The time complexity is O(S), where S is the total number of characters across all words, as we scan each word and character once.

What data structure is most suitable for tracking unique Morse code transformations?

A hash table, or more specifically a set, is ideal for tracking unique Morse code transformations, as it automatically handles duplicates.

How does the pattern of array scanning and hash lookup apply to this problem?

This problem involves scanning each word and transforming each character into Morse code, followed by storing the transformations in a hash table to track uniqueness.

How do we handle duplicate Morse code transformations in the solution?

By using a set, duplicates are automatically ignored, and only unique Morse code transformations are kept.

What are some common mistakes when solving the Unique Morse Code Words problem?

Common mistakes include incorrectly transforming letters into Morse code, not using a hash table to track unique transformations, and failing to account for duplicate transformations.

#804

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

唯一摩尔斯密码词

国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串，比如: 'a' 对应 ".-" ， 'b' 对应 "-..." ， 'c' 对应 "-.-." ，以此类推。为了方便，所有 26 个英文字母的摩尔斯密码表如下： [".-","-...","-.-.","-..…

数组哈希表字符串

题目描述

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

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

lightbulb

解题思路

方法一：哈希表

将 words 所有单词翻译成对应的摩尔斯密码，加入到哈希表中，最后返回哈希表的 size。

时间复杂度 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

class Solution:
    def uniqueMorseRepresentations(self, words: List[str]) -> int:
        codes = [
            ".-",
            "-...",
            "-.-.",
            "-..",
            ".",
            "..-.",
            "--.",
            "....",
            "..",
            ".---",
            "-.-",
            ".-..",
            "--",
            "-.",
            "---",
            ".--.",
            "--.-",
            ".-.",
            "...",
            "-",
            "..-",
            "...-",
            ".--",
            "-..-",
            "-.--",
            "--..",
        ]
        s = {''.join([codes[ord(c) - ord('a')] for c in word]) for word in words}
        return len(s)

speed

复杂度分析

指标	值
时间	O(S)
空间	O(S)

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates the ability to handle string transformation problems using efficient data structures.
question_mark
The candidate shows awareness of array scanning and hash lookup strategies in solving similar problems.
question_mark
The candidate implements a solution that correctly tracks and counts unique transformations without unnecessary complexity.

warning

常见陷阱

外企场景

error
Failing to correctly handle duplicate Morse code transformations, leading to an incorrect count of unique transformations.
error
Not using a hash table (set) to efficiently track unique transformations, resulting in unnecessary complexity or incorrect results.
error
Misunderstanding the Morse code mapping and incorrectly transforming the words into Morse code.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to handle case-sensitive letters and analyze its impact on the solution.
arrow_right_alt
Alter the problem to account for a larger input size and assess if optimizations are necessary.
arrow_right_alt
Consider optimizing the solution further if the input contains many duplicate words.

help

常见问题

外企场景

继续练习

#811 子域名访问计数 #792 匹配子序列的单词数 #819 最常见的单词