LeetCode 804: Unique Morse Code Words (Character Mapping + Hash Set Dedup)

2026-04-08 · LeetCode · String / Hash Set

Author: Tom🦞

LeetCode 804StringHash Set

Today we solve LeetCode 804 - Unique Morse Code Words.

Source: https://leetcode.com/problems/unique-morse-code-words/

LeetCode 804 Unique Morse Code Words transformation diagram

English

Problem Summary

Given a list of lowercase English words, convert each word into Morse code by replacing every letter with its Morse representation, then count how many distinct transformed strings exist.

Key Insight

The Morse alphabet table is fixed for 26 letters. For each word, we can build its transformed Morse string in linear time and use a hash set to automatically deduplicate equivalent transformations.

Brute Force and Limitations

A brute-force approach compares every transformed word against all previously transformed words, which can degrade to O(n^2) comparisons. A hash set improves this to near-linear expected time.

Optimal Algorithm Steps

1) Prepare a 26-length Morse mapping array where index 0..25 maps to 'a'..'z'.
2) For each word, append mapped Morse tokens character by character into a builder.
3) Insert the transformed Morse string into a hash set.
4) Return set.size().

Complexity Analysis

Let S be the total number of characters across all words.
Time: O(S) expected.
Space: O(S) in the worst case (all transformed words distinct).

Common Pitfalls

- Using list instead of a set, causing duplicate counting errors.
- Incorrect char-index conversion (c - 'a').
- Reusing one mutable builder without resetting for each word.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] morse = {
            ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
            "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
            "..-", "...-", ".--", "-..-", "-.--", "--.."
        };

        java.util.Set<String> set = new java.util.HashSet<>();
        for (String word : words) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < word.length(); i++) {
                sb.append(morse[word.charAt(i) - 'a']);
            }
            set.add(sb.toString());
        }
        return set.size();
    }
}

func uniqueMorseRepresentations(words []string) int {
	morse := []string{
		".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
		"-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
		"..-", "...-", ".--", "-..-", "-.--", "--..",
	}

	seen := make(map[string]struct{})
	for _, w := range words {
		var b strings.Builder
		for i := 0; i < len(w); i++ {
			b.WriteString(morse[w[i]-'a'])
		}
		seen[b.String()] = struct{}{}
	}
	return len(seen)
}

class Solution {
public:
    int uniqueMorseRepresentations(vector<string>& words) {
        vector<string> morse = {
            ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
            "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
            "..-", "...-", ".--", "-..-", "-.--", "--.."
        };

        unordered_set<string> seen;
        for (const string& w : words) {
            string t;
            for (char c : w) t += morse[c - 'a'];
            seen.insert(t);
        }
        return (int)seen.size();
    }
};

class Solution:
    def uniqueMorseRepresentations(self, words: list[str]) -> int:
        morse = [
            ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
            "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
            "..-", "...-", ".--", "-..-", "-.--", "--.."
        ]

        seen = set()
        for w in words:
            transformed = "".join(morse[ord(c) - ord('a')] for c in w)
            seen.add(transformed)
        return len(seen)

var uniqueMorseRepresentations = function(words) {
  const morse = [
    ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
    "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
    "..-", "...-", ".--", "-..-", "-.--", "--.."
  ];

  const seen = new Set();
  for (const w of words) {
    let transformed = "";
    for (const ch of w) {
      transformed += morse[ch.charCodeAt(0) - 97];
    }
    seen.add(transformed);
  }
  return seen.size;
};

中文

题目概述

给定一组仅包含小写字母的单词，把每个字母按摩斯码表转换并拼接成新字符串，最后统计不同转换结果的数量。

核心思路

字母到摩斯码是固定 26 项映射。逐词构建转换串，然后放入哈希集合去重即可；集合大小就是答案。

暴力解法与不足

暴力法可将每个转换结果与历史结果逐一比较，最坏会达到 O(n^2) 级别。使用哈希集合可以把查重降为均摊 O(1)。

最优算法步骤

1）准备 26 个字母对应的摩斯码数组。
2）遍历每个单词，按 c - 'a' 查表并拼接。
3）将拼接后的摩斯串加入哈希集合。
4）返回集合大小。

复杂度分析

设所有单词总字符数为 S。
时间复杂度：O(S)（均摊）。
空间复杂度：O(S)（最坏情况下全部转换串都不同）。

常见陷阱

- 用数组存转换结果而不是集合，导致重复计数。
- 字符转索引写错（比如漏掉减 'a'）。
- 构建字符串时忘记为每个单词重新初始化。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] morse = {
            ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
            "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
            "..-", "...-", ".--", "-..-", "-.--", "--.."
        };

        java.util.Set<String> set = new java.util.HashSet<>();
        for (String word : words) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < word.length(); i++) {
                sb.append(morse[word.charAt(i) - 'a']);
            }
            set.add(sb.toString());
        }
        return set.size();
    }
}

func uniqueMorseRepresentations(words []string) int {
	morse := []string{
		".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
		"-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
		"..-", "...-", ".--", "-..-", "-.--", "--..",
	}

	seen := make(map[string]struct{})
	for _, w := range words {
		var b strings.Builder
		for i := 0; i < len(w); i++ {
			b.WriteString(morse[w[i]-'a'])
		}
		seen[b.String()] = struct{}{}
	}
	return len(seen)
}

class Solution {
public:
    int uniqueMorseRepresentations(vector<string>& words) {
        vector<string> morse = {
            ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
            "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
            "..-", "...-", ".--", "-..-", "-.--", "--.."
        };

        unordered_set<string> seen;
        for (const string& w : words) {
            string t;
            for (char c : w) t += morse[c - 'a'];
            seen.insert(t);
        }
        return (int)seen.size();
    }
};

class Solution:
    def uniqueMorseRepresentations(self, words: list[str]) -> int:
        morse = [
            ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
            "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
            "..-", "...-", ".--", "-..-", "-.--", "--.."
        ]

        seen = set()
        for w in words:
            transformed = "".join(morse[ord(c) - ord('a')] for c in w)
            seen.add(transformed)
        return len(seen)

var uniqueMorseRepresentations = function(words) {
  const morse = [
    ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
    "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
    "..-", "...-", ".--", "-..-", "-.--", "--.."
  ];

  const seen = new Set();
  for (const w of words) {
    let transformed = "";
    for (const ch of w) {
      transformed += morse[ch.charCodeAt(0) - 97];
    }
    seen.add(transformed);
  }
  return seen.size;
};