文章目录

• 题目
• • 标题和出处
  • 难度
  • 题目描述
  • • 要求
    • 示例
    • 数据范围
• 解法
• • 思路和算法
  • 代码
  • 复杂度分析

题目

标题和出处

标题：唯一摩尔斯密码词

出处：804. 唯一摩尔斯密码词

难度

2 级

题目描述

要求

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

• "a"\texttt{"a"}"a" 对应 ".-"\texttt{".-"}".-"，
• "b"\texttt{"b"}"b" 对应 "-..."\texttt{"-..."}"-..."，
• "c"\texttt{"c"}"c" 对应 "-.-."\texttt{"-.-."}"-.-."，以此类推。

为了方便，所有 26\texttt{26}26 个英语字母对应摩尔斯密码表如下：

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

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

• 例如，"cab"\texttt{"cab"}"cab" 可以写成 "-.-..--..."\texttt{"-.-..--..."}"-.-..--..."，即 "-.-."\texttt{"-.-."}"-.-."、".-"\texttt{".-"}".-" 和 "-..."\texttt{"-..."}"-..." 的连接。我们将这样一个连接过程称作单词翻译。

返回我们可以获得所有不同单词翻译的数量。

示例

示例 1：

输入：words=["gin","zen","gig","msg"]\texttt{words = ["gin","zen","gig","msg"]}words = ["gin","zen","gig","msg"]
输出：2\texttt{2}2
解释：各单词翻译如下：
"gin"→"--...-."\texttt{"gin"} \rightarrow \texttt{"--...-."}"gin"→"--...-."
"zen"→"--...-."\texttt{"zen"} \rightarrow \texttt{"--...-."}"zen"→"--...-."
"gig"→"--...--."\texttt{"gig"} \rightarrow \texttt{"--...--."}"gig"→"--...--."
"msg"→"--...--."\texttt{"msg"} \rightarrow \texttt{"--...--."}"msg"→"--...--."
共有 2\texttt{2}2 种不同翻译："--...-."\texttt{"--...-."}"--...-." 和 "--...--."\texttt{"--...--."}"--...--."。

示例 2：

输入：words=["a"]\texttt{words = ["a"]}words = ["a"]
输出：1\texttt{1}1

数据范围

• 1≤words.length≤100\texttt{1} \le \texttt{words.length} \le \texttt{100}1≤words.length≤100
• 1≤words[i].length≤12\texttt{1} \le \texttt{words[i].length} \le \texttt{12}1≤words[i].length≤12
• words[i]\texttt{words[i]}words[i] 由小写英语字母组成

解法

思路和算法

为了得到不同单词翻译的数量，需要将数组 words\textit{words}words 中的所有单词使用摩尔斯密码翻译，记录所有的单词翻译，去除重复项之后统计不同单词翻译的数量。

创建数组存储全部英语字母对应摩尔斯密码表，然后对于每个单词，遍历单词中的每个字母，得到每个字母对应的摩尔斯密码，连接之后即可得到单词翻译。

为了去除重复的单词翻译，使用哈希集合存储每个单词的单词翻译，哈希集合中的任意两个单词翻译都是不同的。遍历全部单词之后，哈希集合内的元素个数即为不同单词翻译的数量。

代码

class Solution {public int uniqueMorseRepresentations(String[] words) {String[] morseArray = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};Set set = new HashSet();for (String word : words) {StringBuffer sb = new StringBuffer();int length = word.length();for (int i = 0; i < length; i++) {char c = word.charAt(i);sb.append(morseArray[c - 'a']);}set.add(sb.toString());}return set.size();}
}

复杂度分析

• 时间复杂度：O(∑lw+∑lm)O(\sum l_w + \sum l_m)O(∑lw​+∑lm​)，即数组 words\textit{words}words 中所有单词的长度之和与所有单词对应的单词翻译的长度之和。需要 O(∑lw)O(\sum l_w)O(∑lw​) 的时间遍历所有单词，对于每个单词，生成单词翻译和存入哈希表的时间为该单词对应的单词翻译的长度，因此对所有单词生成单词翻译和存入哈希表的时间为 O(∑lm)O(\sum l_m)O(∑lm​)。总时间复杂度为 O(∑lw+∑lm)O(\sum l_w + \sum l_m)O(∑lw​+∑lm​)。

• 空间复杂度：O(∑lm)O(\sum l_m)O(∑lm​)，即数组 words\textit{words}words 中所有单词对应的单词翻译的长度之和。需要使用哈希表存储每个单词对应的单词翻译，最坏情况下，每个单词对应的单词翻译都不同，此时哈希表的空间为所有单词对应的单词翻译的长度之和。