Python Beginner Algorithms Tutorial

Find Words Formed by Characters (via Leetcode)

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

"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

"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

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

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
In [8]:
assert find_words_formed_by_characters(words=['hi', 'help', 'hello'], chars='hlope') == 4