1002_Find_Common_Characters

1002. Find Common Characters

该题目要在由字符串组成的数组中，找到所有字符串都存在的字符，包括重复的。下边给出两种解法

解法 1

这个也是首先想到的，但是效率不高

1. 生成一个数组 arrayWithMap，这个数组中放字典
2. 这个字典中，key 为字符，value 为这个字符在这个字符串中出现的次数
3. 随机选取一个字符串（第一个），遍历这个字符串，取得的每一个字符去 arrayWithMap 中遍历，看每一个 map 是否存在该字符，如果存在，则对应map 的中 该字符 对应的 value - 1，当 value 为 0 时，移除，如果都存在，则该字符就是公共字符，放入数组中

func commonChars(A []string) []string {
	resultArray := make([]string, 0)
	arrayWithMap := make([]map[rune]int, len(A))

	for idx, str := range A {
		charMap := make(map[rune]int, 0)
		for _, char := range str {
			num, ok := charMap[char]
			 if ok {
				 charMap[char] = num + 1
			 } else  {
			 	charMap[char] = 1
			 }
		}
		arrayWithMap[idx] = charMap
	}

	for _, char := range A[0] {
		exist := true
		for _, charMap := range arrayWithMap {
			num, ok := charMap[char]
			if ok && num > 0 {
				charMap[char] = num - 1
			} else  {
				delete(charMap, char)
				exist = false
				break
			}
		}
		if exist {
			resultArray = append(resultArray, string(char))
		}
	}
	return resultArray
}

解法 2

解法一提交上去发现，不管是时间还是空间，消耗都非常巨大，只打败了 46% 左右的人。后来看了第一名的解法，发现，真是个人才。

1. 考虑到字母有 26 个，首先生成一个长度为 26 的数组 m，数组中存一个大数
2. 遍历数组 A，把每一个字符串映射到一个数组temp 中，数组的索引代表 a - z，而对应的值，代表该字母在字符串中出现的次数。
3. 然后把这个数组 temp 和 m 逐位比较，取值小的哪一位，因为重复次数，总要以小的为主，比如 look 中 o 存在 2 次，而 hour 中，o 存在 1 次，所以在结果中 o 最多出现 1 次。
4. 当我们比较完之后，数组 m 中，值不为 0 的下标就是共同出现的字母，而对应的非 0 值，就是该字母出现的次数。

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func commonChars(A []string) []string {
	m := make([]int, 26)

	for i := 0; i < 26; i++ {
		m[i] = (1 << 31) - 1
	}

	for _, str := range A {
		tmp := make([]int, 26)
		for _, c := range str {
			tmp[byte(c)-'a']++
		}
		for c, num := range tmp {
			m[c] = min(num, m[c])
		}
	}

	out := make([]string, 0)
	for idx, count := range m {
		if count > 0 {
			for i := count; i > 0; i-- {
				out = append(out, string(byte(idx + 'a')))
			}
		}

	}
	return out
}

不得不说，是真的强 👍