leetcode 804. 唯一摩尔斯密码词

leetcode 804. 唯一摩尔斯密码词.

题目描述

804. 唯一摩尔斯密码词

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

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

解题思路

法1

方法1:哈希表:\

这个题是让我们计算摩尔斯密码的种类,比如说"gin" -> "--...-."; "zen" -> "--...-.",他们的摩尔斯密码相同,也就是一种,

1. 建立一个map储存摩尔斯密码的种类,map[string]bool,key为摩尔斯密码,value表示是否出现过,

2. 遍历所有的单词,并将其转化为摩尔斯密码,在将对应的摩尔斯密码map中的value赋值为true

3. 最后遍历输出map的长度就是答案结果

• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

func uniqueMorseRepresentations(words []string) int {
 morseCodes := []string{".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."}
 uniqueTranslations := make(map[string]bool)

 for _, word := range words {
  translation := ""
  for _, ch := range word {
   index := ch - 'a'
   translation += morseCodes[index]
  }
  uniqueTranslations[translation] = true
 }

 return len(uniqueTranslations)
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 2.2 MB , 在所有 Go 提交中击败了 57.14% 的用户 通过测试用例： 82 / 82 炫耀一下: