【刷题日记】804. 唯一摩尔斯密码词

本次刷题日记的第 29 篇，力扣题为：804. 唯一摩尔斯密码词 ，简单

一、题目描述：

今天周日，咱们也要保持习惯，leetcode 的今天每日一题是 一摩尔斯密码词，乍一看我们是不是也可以解密摩尔斯密码了？感觉有点意思

周日，leetcode 也想让咱放松一下，刷一个比较还理解的题目，一起来看看

二、这道题考察了什么思想？你的思路是什么？

这道题，给出了哪些重要点的信息呢：

• 给出了从字母 a 到 字母 z 对应的字符串映射关系，这个映射关系我们不用刻意关注，哪怕变成其他的映射关系也无所谓，重点是我们只是他们是一一映射的就可以了
• 题目要求，给出单词，我们要转换成对应的字符串，且在给出的单词数组中，不同的单词，可能存在相同的拼接结果字符串，那么，我们需要计算出，这些结果字符串中，不同种类的字符串翻译

看到上述给出的重点信息，对应让我们从字母或者单词，按照映射关系翻译成对应的字符串，这个没有啥好说的

直接写一个帮助列表，a-z 的字母，正好对应0-25 的列表索引，根据索引找到对应字符串，最后拼接起来即可

例如这样

那么我们可以很轻易的的拼接成字符串了，如何找到出不同的字符串呢？

我们可以使用 hash 表来进行解决，hash 表的话，我们直接就可以使用 golang 中的 map 可以处理， c++ 中的 set 也可以处理，只要 key 是不会重复的就可以处理了

按照上述的思路，我们就可以很明确的得到这题的解决方式了，接下来，咱们就将上述思路，翻译成代码即可，思路还是很清晰的吧

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，编码的时候，这里需要注意

• 需要创建好一个帮助列表，存放，每一个字母对应的字符串
• 使用 hash 表来处理和提取结果字符串的种类

编码如下：

func uniqueMorseRepresentations(words []string) int {
    // 先写一个帮助列表
    var helper = []string{
        ".-", "-...", "-.-.", "-..", ".", "..-.", "--.",
        "....", "..", ".---", "-.-", ".-..", "--", "-.",
        "---", ".--.", "--.-", ".-.", "...", "-", "..-",
        "...-", ".--", "-..-", "-.--", "--..",
    }
    m := map[string]int{}
    // 遍历单词
    for _,word := range words {
        // 开始处理每一个单词
        tmp := ""
        for _,ch := range word {
            tmp += helper[ch - 'a']
        }
        m[tmp]++
    }
    return len(m)
}

看完上述编码，还是很简单明了的，但是写过 golang 的兄弟，知道咱们直接拼接字符串效率是比较低， 我们可以使用 golang 自带的库， strings ，将上述关键代码替换成这样

css

复制代码

tmp := &strings.Builder{}tmp.WriteString(helper[ch-'a'])m[trans.String()]++

使用 strings.Builder 和 直接使用拼接字符串相比  strings.Builder 效率会高很多，具体原因是为什么，xdm 可以思考一下

四、总结：

此处，我们可以看到本题的时间复杂度是 O(S) ，此处的 S 可不是 单词的数量，而是每个单词的字符长度和，仔细看上述编码，咱们其实遍历的是每个单词的字符

此处的空间复杂度也是 O(S) ，我们创建的 tmp 字符串，开辟的空间也是如此

原题地址：804. 唯一摩尔斯密码词

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~