题目描述
leetcode 第1002题:查找常用字符
给定仅有小写字母组成的字符串数组 A,返回列表中的每个字符串中都显示的全部字符(包括重复字符)组成的列表。例如,如果一个字符在每个字符串中出现 3 次,但不是 4 次,则需要在最终答案中包含该字符 3 次。
你可以按任意顺序返回答案。
示例:
输入:[“bella”,”label”,”roller”]
输出:[“e”,”l”,”l”]
解题方法
哈希表
参照题解
- 解题思路
由于数组
A
中的字符串只包含小写字母
先统计26个小写字母中,每个字母c
在所有字符串中最小出现的次数minfreq[c]
,初始为无限大
遍历A
中的每个字符串word
,使用freq[c]
统计每个字母c
在当前word
中出现的次数freq[c]
统计完成后,对于每个c
在每个word
中出现的次数freq[c]
,一定不小于它在所有字符串中出现的次数minfreq[c]
所以将每个minfreq[c]
与freq[c]
做比较取最小值
最终将minfreq
中每个字母乘以它出现的次数依次存入列表ans
返回
- 复杂度
时间复杂度:O(m(n+Z)),m为数组A的长度,n为字符串的平均长度,Z为小写字母的长度
空间复杂度:0(Z),Z为小写字母的长度
- 代码实现
python3
1 | class Solution: |
php
1 | class Solution { |