Program to find Possible Words using given characters

In this tutorial, you will learn to write a Python program that will display all the possible words using some given characters. From a given list of words and a character array, we have to find and print all the words in that list that are possible using the characters from the array. Repetition of characters will be not allowed.

Look at the sample input-output format.

Input:

words=['pot', 'pale', 'pan', 'spa', 'act']

charset=['a', 'p','s', 'n' ]

Output: pan spa

Input:

words=['top', 'cat', 'mat', 'hat']

charset=['p', 'o', 't', 'h']

Output: top

To solve this problem, first, convert the list of words in a dictionary using the Counter() method. We will traverse the words in the list one by one and after converting to a dictionary, we will check if all the keys of any word are in the given set of characters. This means that a word is possible to make from the given array of characters.

Algorithm

Look at the algorithm to understand the working of the approach.

Step 1- Define functions to count characters in words and to check if the word is possible from the given set

Step 2- Count the characters of every word in the list using a dictionary and the defined function

Step 3- Create a dictionary of words where the characters are the keys

Step 4- From the dictionary, we will find words whose all keys are in the given character set

Step 5- Print the words whose all characters are in the given character set

Step 6- Declare a list of strings and a character array from which all possible words will be displayed

Step 7- Pass the list and the character array in the function

Python Program

In this program, we have defined two separate functions for counting characters in a word and to find the words which can be made from the given character array. We have used a dictionary to solve this problem.

We have converted the given list of words into a dictionary using the built-in Python Counter() method. To check if all the keys are in the character set, we have used a flag variable which will be used to print the final result.

def Countchar(word):
    dict = {}
    for i in word:
        dict[i] = dict.get(i, 0) + 1
    return dict
def find_words(word_list, charSet):
    for word in word_list:
        flag = 1
        chars = Countchar(word)
        for key in chars:
            if key not in charSet:
                flag = 0
            else:
                if charSet.count(key) != chars[key]:
                    flag = 0
        if flag == 1:
            print(word)
# input            
word_list = ['mat', 'boy', 'bat', 'goal', 'get', 'got', 'orange']
charSet = ['e', 'o', 'b', 'a', 'g', 'l', 't']
find_words(word_list, charSet)

bat
goal
get
got

Conclusion

In this tutorial, we have learned how to display all the words from a given list that are possible to make from a given set of characters. To execute this problem we have used a dictionary, and Counter() method in our program.