拼写单词
来源 leetcode 1160.拼写单词
思路
遇到字符串仅包含小写（或者大写）英文字母的题，都可以试着考虑构造长度为 26 的数组。这样，数组每个位置分别代表一个字母，统计出字母出现的次数，方便后面问题的解决。
本题中，既要统计“字母表”中字母出现的次数，也要统计单词中字母出现的次数。如果字母表中字母出现的次数大于等于单词中每种字母出现的次数，那么这个单词就可以由字母表拼写出来。
以字母表 “atach” 和 词汇 “cat” 为例，整个过程图示如下：
my ugly code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
class Solution(object):
def countCharacters(self, words, chars):
"""
:type words: List[str]
:type chars: str
:rtype: int
"""
res = []
for word in words:
if self.check_word_in_chars(word, chars):
res.append(word)
count = 0
for word in res:
count += len(word)
return count
def check_word_in_chars(self, word, chars):
wordDict = {}
charsDict = {}
for wordChar in word:
if wordDict.get(wordChar) == None:
wordDict[wordChar] = 1
else:
wordDict[wordChar] += 1
for char in chars:
if charsDict.get(char) == None:
charsDict[char] = 1
else:
charsDict[char] += 1
# 检查字母表里面字母出现的次数是不是大于词汇中字母出现的次数
flag = False
wordLength = len(wordDict)
count = 0
for wchar in wordDict:
if charsDict.get(wchar) and wordDict.get(wchar):
if charsDict[wchar] >= wordDict[wchar]:
count += 1
if count == wordLength:
flag = True
return flag
|
明显上述代码效率就不高，经历了循环嵌套，而且相关实现代码重复啰嗦， 甚至会达到O(n^2)的复杂度；
高手思路赏析
解题思路
显然，对于一个单词 word，只要其中的每个字母的数量都不大于 chars 中对应的字母的数量，那么就可以用 chars 中的字母拼写出 word。所以我们只需要用一个哈希表存储 chars 中每个字母的数量，再用一个哈希表存储 word 中每个字母的数量，最后将这两个哈希表的键值对逐一进行比较即可。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
chars_cnt = collections.Counter(chars)
ans = 0
for word in words:
word_cnt = collections.Counter(word)
for c in word_cnt:
if chars_cnt[c] < word_cnt[c]:
break
else:
ans += len(word)
return ans
|
复杂度分析