【刷题日记】 最常见的单词

本次刷题日记的第 36 篇，力扣题为：最常见的单词 ，简单

一、题目描述：

最常见的单词题目，乍一看，咱们还以为是要在浩如烟海的词典中，查找出现频率在某个范围中的单词呢，仔细一看，好像不用那么复杂，看上去还是非常简单好理解的

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

瞅瞅主题给我们讲述了哪些重要的信息：

• 题目给出一个段落，这个段落可能包含多个单词，也可能包含一个单词，单词中有大写和小写
• 题目还给出了一个禁用单词列表，是小写的，我们需要找出上述段落中，出现频率最高的单词，且不在禁用列表中的单词，此处就需要注意对于比较和校验的时候，需要将原有的大写字母转成小写字母

题意非常明确，看到题目中有说到计算单词的频率的时候，其实我们可能就会有条件反射了，这种题目大概率是要使用 哈希表的

仔细分析一下，我们需要做这么 2件 事情：

• 明确找到每一个单词，并计算每一个单词出现的频率

找到单词比较容易，我们可以在遍历段落字符串的时候，用一个临时切片来存放遍历的字母，当我们校验到当前字符是空格，或者是其他非字母字符的时候，我们就可以确定，临时切片中的数字，已经是一个完整的单词了

计算单词出现频率，将上述找到的单词放入哈希表记个数就行了

• 如何找到最大的出现次数的单词呢，还不能是被禁用的

通过上述的遍历，和哈希表的处理，我们就可以用一个变量来存储出现频次最大的数字，后续遍历 哈希表的时候，就可以拿出来进行比对，找到对应的字符串，我们就可以实现这个题的要求了

上述思路还是比较清晰的，虽然没有图，但是文字已经能够简单的表达出思路了，接下来就开始撸代码吧

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，此处的编码需要注意的是，咱们遍历段落循环的控制，我们可以根据判断当前字符不是字母的情况下，来校验当前是否已经找到一个单词

但是，我们需要注意的是，如果段落中，只有一个单词的时候，我们需要处理好这种场景

例如，我们可以遍历的时候，控制可以让索引等于段落字符串的长度，具体带编码细节

func mostCommonWord(paragraph string, banned []string) string {
    // 记录 banded 的字符
    bm := map[string]bool{}
    for _, b := range banned {
        bm[b] = true
    }
    // 记录段落的长度
    length := len(paragraph)
    // 定义记录单词评率的 map
    helper := map[string]int{}
    var tmp []byte
    var maxFreq int
    // 此处控制的循环就可以是 等于 length 的， 原因是，当给出的段落中就只有一个单词的时候，我们也是要进行处理的
    for i:=0; i<=length; i++ {
        // 判断如果是字母，则咱们继续将该字母加入到 tmp 切片中
        if  i<length && unicode.IsLetter(rune(paragraph[i])){
            tmp = append(tmp,byte(unicode.ToLower(rune(paragraph[i]))))
        }else if tmp != nil{
            // 不是字母的时候，说明这个时候已经是空格了，那么 tmp 已经是一个单词了，此时就要处理改单词出现频率的事情了
            // 还需要查看该字符串是否被禁用了
            s := string(tmp)
            if !bm[s]{
                helper[s]++
                maxFreq = max(maxFreq,helper[s])
            }
            tmp = nil
        }
    }
    for s,v := range helper{
        if maxFreq == v{
            return s
        }
    }
    return ""
}
// 写一个比较数字的函数
func max(a,b int) int {
    if a>b {
        return a
    }
    return b
}

咱们编码的思路可以理解是这样的

• 先将被禁用的单词，用一个 map 来记录一波
• 再遍历段落字符串，计算出对应单词出现的频率，存放到 helper 哈希表中，和记录最大频率的数值
• 遍历 helper 哈希表，判断未被禁用的字符串出现的频率是否等于目前记录的最大频率，若是，则返回该字符串

四、总结：

这种实现方式的时间复杂度是多少呢，我们可以看到，题目中的实现，我们要是对于给出的禁用列表做了一次遍历，对于题目给出的段落字符串进行了一次遍历，那么咱们的时间复杂是 O(m+n)

空间复杂度也是同样的道理，咱们引入了 2 个 map，产生了空间消耗，则咱们的空间复杂度也是 O(m+n) ， m 表示 禁用列表的长度， n 表示段落字符串的长度

原题地址：819. 最常见的单词

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

欢迎点赞，关注，收藏

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

好了，本次就到这里

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

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