Find Words Formed by Characters (via Leetcode)¶

Date published: 2020-04-13

Category: Python

Subcategory: Beginner Algorithms

Tags: functions, loops, dictionaries

Problem on Leetcode.

Problem statement:

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 words.

Test Cases¶

In [3]:

# assert find_words_formed_by_characters(words=["cat", "bt", "hat", "tree"], chars="atach") == 6

# assert find_words_formed_by_characters(words=["cat", "bt", "hat", "tree"], chars="atach") == 6

"cat" and "hat" exist in chars. The count of letters is 3 and 3 respectively and the sum of those is 6.

In [4]:

# assert find_words_formed_by_characters(words=['hi', 'help', 'hello'], chars='hlope') == 4

# 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.

Pseudocode¶

In [5]:

# 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

# 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

Code¶

In [6]:

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

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

Complexity¶

Let n be the count of items in words, m be the max length of characters in an item in words, and b be the length of characters in chars.

Time complexity:

• O(b) operation to iterate over each characters in chars
• An iteration over each word in words and then each letter in the word is O(nm)

Time complexity is O(nmb).

Space complexity:

• O(bm) complexity for size of chars_default_dict created m time for each word in words.

Space complexity is O(bm).

Run Test Cases¶

In [7]:

assert find_words_formed_by_characters(words=["cat", "bt", "hat", "tree"], chars="atach") == 6

assert find_words_formed_by_characters(words=["cat", "bt", "hat", "tree"], chars="atach") == 6

In [8]:

assert find_words_formed_by_characters(words=['hi', 'help', 'hello'], chars='hlope') == 4

assert find_words_formed_by_characters(words=['hi', 'help', 'hello'], chars='hlope') == 4