Problem on Leetcode.
You are provided a list of
words and random letters in
chars. You want to find if the letters in
chars exist in each word in
words and output a sum of those letters across
# assert find_words_formed_by_characters(words=["cat", "bt", "hat", "tree"], chars="atach") == 6
"hat" exist in
chars. The count of letters is 3 and 3 respectively and the sum of those is 6.
# assert find_words_formed_by_characters(words=['hi', 'help', 'hello'], chars='hlope') == 4
"help" exists in
chars. The count of letters in
"help" is 4.
# create function with arguments for words and chars # assign characters_good_words_sum to 0 # this will our running total of count of characters in words that are in chars... # for word in words: # we want to reset our dictionary to keep track of unique occurences of letters in chars # cast chars to a dict to be a count of unique letters... # chars_default_dict = defaultdict(int) # for char in chars: # chars_default_dict[char] += 1 # set a boolean variable to True to mark all letters in word found in chars # for each index and letter in enumerate(word): # if letter in chars_default_dict_update: # if value at chars_default_dict_update[letter] is greater than 1: # reduce value by 1 # else: # delete key from chars_default_dict_update # else: # letter wasn't found in chars_default_dict_update... # we want to advance to next word... # set boolean to False # break # if boolean value is True: # this means we reached last index in iteration and all letters in word in chars... # find count of word and append to characters_good_words_sum # return characters_good_words_sum
from collections import defaultdict def find_words_formed_by_characters(words, chars): characters_good_words_sum = 0 for word in words: chars_default_dict = defaultdict(int) for char in chars: chars_default_dict[char] += 1 all_letters_in_word_found_in_chars = True for index, letter in enumerate(word): if letter in chars_default_dict: if chars_default_dict[letter] > 1: chars_default_dict[letter] -= 1 else: del chars_default_dict[letter] else: all_letters_in_word_found_in_chars = False break if all_letters_in_word_found_in_chars is True: characters_good_words_sum += len(word) return characters_good_words_sum
n be the count of items in
m be the max length of characters in an item in
b be the length of characters in
- O(b) operation to iterate over each characters in
- An iteration over each word in
wordsand then each letter in the word is O(nm)
Time complexity is O(nmb).
- O(bm) complexity for size of
mtime for each word in
Space complexity is O(bm).
assert find_words_formed_by_characters(words=["cat", "bt", "hat", "tree"], chars="atach") == 6
assert find_words_formed_by_characters(words=['hi', 'help', 'hello'], chars='hlope') == 4