LeetCode-1002. 查找常用字符(Golang)

一、前言

作者：bug菌 博客：CSDN、掘金、infoQ、51CTO等 简介：CSDN/阿里云/华为云/51CTO博客专家，博客之星Top30，掘金年度人气作者Top40，51CTO年度博主Top12，掘金/InfoQ/51CTO等社区优质创作者，全网粉丝合计10w+

       哈喽，小伙伴们，我是bug菌呀👀。金三银四，又到了刷题月啦。所以不管你是准备跳槽还是在职，都一起行动起来，顺应这个时代月干点该干的事儿👣。所以，赶紧跟着bug菌的步伐卷起来吧⏰，变强从这一刻开始！➕🧈

       小伙伴们在批阅文章的过程中如果觉得文章对您有一丝丝帮助，还请别吝啬您手里的赞呀，大胆的把文章点亮👍吧，您的点赞三连(收藏⭐️+关注👨🎓+留言📃)就是对bug菌我创作道路上最好的鼓励与支持😘。时光不弃🏃🏻♀️，创作不停💕，加油☘️

🏆本文收录于《LeetCode每日一题》，专门攻坚算法提升，带着你一块儿刷题。

二、题目描述

给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。

示例 1：

输入：words = ["bella","label","roller"]
输出：["e","l","l"]

示例 2：

输入：words = ["cool","lock","cook"]
输出：["c","o"]

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] 由小写英文字母组成

三、思路分析

就是挨个挨个取两数的交集 ，拿着去匹配下一个元素，直到匹配到最后，就是答案所在！

细节看代码， 不是很优雅，不断在优化，这是第一版，后期更新！

四、算法实现

func commonChars(A []string) []string {
	m := make(map[string]int)
	var l []string
	//用于初始化m1
	var index = 0
	for i := 0; i < len(A); i++ {
		index++
		m = getOther(index, m, A[i])
	}
	//m 即返回的 公共字符个数
	for k, v := range m {
		//大于1的既多append几次
		if v > 1 {
			for i := 0; i < v; i++ {
				l = append(l, k)
			}
		} else {
			l = append(l, k)
		}
	}
	return l
}

func getOther(index int, m map[string]int, s string) map[string]int {
	//用于统计字符串s的字母数量集
	m1 := make(map[string]int)
	//m2表示上一个交集与该字符串的公共结果集
	m2 := make(map[string]int)
	for i := 0; i < len(s); i++ {
		m1[string(s[i])]++
	}
	//初始化，一开始交集为空，所以用index作为条件判断，把第一个字符串的字母数量集返回过去
	if index == 1 {
		return m1
	}
	for k, v1 := range m1 {
		//判断新字符串中是否含有交集中的字母
		v2, ok := m[k]
		//如果key存在，则比较value（即字母个数），取交集（个数少即公共元素）
		if ok {
			if v1 <= v2 {
				m2[k] = v1
				continue
			}
			m2[k] = v2
		}
	}
	//返回交集
	return m2
}

执行结果截图：

五、复杂度分析

时间复杂度：O(n(m+∣Σ∣))，其中 n 是数组 A 的长度（即字符串的数目），m 是字符串的平均长度，Σ 为字符集，在本题中字符集为所有小写字母，∣Σ∣=26。

• 遍历所有字符串并计算 freq 的时间复杂度为 O(nm)；
• 使用 freq 更新 minfreq 的时间复杂度为 O(n∣Σ∣)；
• 由于最终答案包含的字符个数不会超过最短的字符串长度，因此构造最终答案的时间复杂度为 O(m+∣Σ∣)。这一项在渐进意义上小于前二者，可以忽略。

空间复杂度：O(∣Σ∣)，这里只计算存储答案之外的空间。我们使用了数组 freq 和 minfreq\，它们的长度均为 ∣Σ∣。

六、小结

力扣惯例，简单题从来不简单，困难题比想象更困难。

        一个人刷可能会觉得很累很难坚持，但是一群人刷就会觉得它是一件很有意义的事儿，互相督促互相鼓励，一起变强。

        我是bug菌，一名想走👣出大山改变命运的程序猿。接下来的路还很长，都等待着我们去突破、去挑战。来吧，小伙伴们，我们一起加油！未来皆可期，fighting！