LeetCode题解(1160)：判断可由指定字母拼写的所有单词总长(Python)-白红宇

LeetCode题解(1160)：判断可由指定字母拼写的所有单词总长(Python)

阅读量：1900 次

发布时间：2019-04-26

本文共 1425 字，大约阅读时间需要 4 分钟。

题目：（简单）

解法	时间复杂度	空间复杂度	执行用时
Ans 1 (Python)	$O (N \times K + C)$ : K为单词平均长度，C为chars长度	$O (C)$ : C为chars的长度	400ms (9.72%)
Ans 2 (Python)	$O (N \times K + C)$ : K为单词平均长度，C为chars长度	$O (C)$ : C为chars的长度	196ms (60.88%)
Ans 3 (Python)	$O (N \times K + C)$ : K为单词平均长度，C为chars长度	$O (C)$ : C为chars的长度	104ms (98.39%)

LeetCode的Python执行用时随缘，只要时间复杂度没有明显差异，执行用时一般都在同一个量级，仅作参考意义。

解法一（使用collections.Counter类）：

def countCharacters(self, words: List[str], chars: str) -> int:    pattern = collections.Counter(chars)    ans = 0    for word in words:        count = pattern & collections.Counter(word)        if len(list(count.elements())) == len(word):            ans += len(word)    return ans

解法二（哈希表计数）：

def countCharacters(self, words: List[str], chars: str) -> int:    pattern = collections.Counter(chars)    ans = 0    for word in words:        count = pattern.copy()        for c in word:            if c not in count or count[c] <= 0:                break            else:                count[c] -= 1        else:            ans += len(word)    return ans

解法三（更好的哈希表计数）：

def countCharacters(self, words: List[str], chars: str) -> int:    pattern = collections.Counter(chars)    ans = 0    for word in words:        for c in word:            if c not in pattern or word.count(c) > pattern[c]:                break        else:            ans += len(word)    return ans

转载地址：http://yqgdf.baihongyu.com/

你可能感兴趣的文章

Javascript 之 Array - entries()、every()、filter()

查看>>

ReferenceError: Unknown plugin component

查看>>

Cannot find module @babel/helper-module-imports

查看>>