You are given an array of strings words
and a string chars
.
A string is good if it can be formed by characters from chars
(each character can only be used once).
Return the sum of lengths of all good strings in words
.
Example 1:
Input: words = ["cat","bt","hat","tree"], chars = "atach" Output: 6 Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.
Example 2:
Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr" Output: 10 Explanation: The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.
Note:
1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
- All strings contain lowercase English letters only.
Solution: Hashtable
Use a hashtable to store each letter’s frequency of the string and compare that with each word.
Time complexity: O(n + sum(len(word))
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua, 72 ms, 20 MB class Solution { public: int countCharacters(vector<string>& words, string chars) { vector<int> counts(26); for (char c : chars) ++counts[c - 'a']; int ans = 0; for (const string& word : words) { vector<int> cur(26); bool valid = true; for (char c: word) if (++cur[c - 'a'] > counts[c - 'a']) { valid = false; break; } if (valid) ans += word.length(); } return ans; } }; |
Python#
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# Author: Huahua class Solution: def countCharacters(self, words: List[str], chars: str) -> int: counts = collections.Counter(chars) def isValid(word): cur = collections.Counter(word) for c in cur: if c not in counts or cur[c] > counts[c]: return False return True ans = 0 for word in words: ans += len(word) if isValid(word) else 0 return ans |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment