Published: Sep 24, 2022
This is a sort of anagram problem. A hash table is a good data structure to solve this problem. Two types of hash tables are necessary: one for the given chars, another for the each word. If we compare these two hash tables, it’s not difficult to find the answer.
You are given an array of strings
wordsand 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.
1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
charsconsist of lowercase English letters.
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.
The first step is to create a character frequency table for
To check each word in the word list, create another frequency table for the word.
All characters in the word table exist in the first frequency table, also the count is greater than or equal to,
then add the word length to the result.
class FindWordsThatCanBeFormedByCharacters: def countCharacters(self, words: List[str], chars: str) -> int: counter = collections.Counter(chars) def isGood(word): w_cnt = collections.Counter(word) for k, v in w_cnt.items(): if k not in counter or counter[k] < v: return False return True result = 0 for word in words: if isGood(word): result += len(word) return result
O(m + n)– m: length of chars, n: number of words
O(m + k)– k : length of each word