应用题-哈希表-查找共用字符

管理员
下述解法中,统计出现次数使用的是defaultdict。 由于本题的特殊性`words[i] 由小写英文字母组成`,哈希表的实现可以用长度为26的数组实现。 ```python from collections import defaultdict class Solution: # 字符串数组words,请找出所有在words的每个字符串中都出现的共用字符(包括重复字符),并以数组形式返回。可以任意顺序返回答案。 def commonChars(self, words: List[str]) -> List[str]: # 统计每个单词中字母出现次数 # 所有单词中字母出现的次数对比,次数取出现的最小次数 times = defaultdict( int ) for v in words[ 0 ]: times[ v ] += 1 # 利用第一个单词初始化times n = len( words ) for i in range( 1, n ): # 统计words[i]中字母出现的次数 times和当前的对比 确定最终出现次数 cur_times = defaultdict( int ) for v in words[ i ]: cur_times[ v ] += 1 for k, v in times.items(): # times中的字母在cur_times中也出现 有共同字母取两者最小的 反之为0 times[ k ] = min( cur_times[ k ], v ) if k in cur_times else 0 ans = [] for k, v in times.items(): if v > 0: for _ in range( v ): ans.append( k ) return ans ```
评论 0

发表评论 取消回复

Shift+Enter 换行  ·  Enter 发送
还没有评论,来发表第一条吧