1002.查找共用字符

一、问题描述

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

示例：

输入：["flower","flow","flight"]
输出："fl"

提示：

• 1 <= A.length <= 100
• 1 <= A[i].length <= 100
• A[i] 和 A[j] 由小写英文字母组成。

二、方案一：计数法

1、思路

计数法是统计每个字符串中每个字符的出现次数，然后找出所有字符串中每个字符的最小出现次数。这种方法利用了字符集有限（只有小写英文字母）的特点，大大提高了效率。

2、代码实现

func commonChars(words []string) []string {
	// 初始化计数器
	minfreq := [26]int{}
	for i := 0; i < 26; i++ {
		minfreq[i] = math.MaxInt32
	}
	for _, word := range words {
		freq := [26]int{}
		for _, c := range word {
			freq[c-'a'] += 1
		}
		fmt.Println(1111, freq)
		for k, v := range minfreq {
			if freq[k] < v {
				minfreq[k] = freq[k]
			}
		}
	}

	var strings []string
	for k, v := range minfreq {
		for j := 1; j <= v; j++ {
			strings = append(strings, string(k+'a'))
		}

	}

	return strings
}

3、复杂度分析

• 时间复杂度：O(n*m)，其中 n 是字符串数组 A 的长度，m 是字符串的平均长度。
• 空间复杂度：O(1)，因为我们只使用了固定大小的数组来存储字符频率。

四、总结

方案	时间复杂度	空间复杂度	优点	缺点
计数法	O(n*m)	O(1)	效率高，适用于大规模数据	实现相对复杂

推荐使用计数法，因为它在处理大规模数据时更加高效。