Given a dictionary and a character array, print all valid words that are possible using characters from the array. Note: Repetitions of characters is not allowed. Examples:
Input : Dict = ["go","bat","me","eat","goal","boy", "run"]
arr = ['e','o','b', 'a','m','g', 'l']
Output : go, me, goal.
This problem has existing solution please refer Print all valid words that are possible using Characters of Array link. We will this problem in python very quickly using Dictionary Data Structure. Approach is very simple :
- Traverse list of given strings one by one and convert them into dictionary using Counter(input) method of collections module.
- Check if all keys of any string lies within given set of characters that means this word is possible to create.
Python
# Function to print words which can be created# using given set of charactersdef charCount(word): dict = {} for i in word: dict[i] = dict.get(i, 0) + 1 return dictdef possible_words(lwords, charSet): for word in lwords: flag = 1 chars = charCount(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)if __name__ == "__main__": input = ['goo', 'bat', 'me', 'eat', 'goal', 'boy', 'run'] charSet = ['e', 'o', 'b', 'a', 'm', 'g', 'l'] possible_words(input, charSet) |
Output:
go me goal
Time complexity: O(n^2)
Space complexity: O(n)
Recursive approach:
First, we define a function find_words(dictionary, characters, word=”) that takes in three arguments:
- dictionary: a list of strings representing the valid words that can be formed from the given characters
- characters: a list of characters that can be used to form the words
- word: a string representing the current combination of characters being checked (initially empty)
The function has two cases:
- The base case: if word is in the dictionary, it means that we have found a valid word, so we print it.
- The recursive case: for each character in the characters list, we create a copy of the characters list called new_characters and remove the current character from it. We then call find_words again with the new_characters list and the current word appended with the current character. This will recursively check all possible combinations of characters to see if they form a word in the dictionary.
Finally, we have an example of how to use the find_words function, where we define the dictionary and characters lists and call find_words with those lists as arguments.
Python3
def find_words(dictionary, characters, word=''): # base case: if the word is in the dictionary, print it if word in dictionary: print(word) # recursive case: for each character in the characters list, make a new list of characters # with that character removed, and call find_words with the new list of characters and the # current word appended with the current character for char in characters: new_characters = characters.copy() new_characters.remove(char) find_words(dictionary, new_characters, word + char)# example usagedictionary = ["go","bat","me","eat","goal","boy", "run"]characters = ['e','o','b', 'a','m','g', 'l']find_words(dictionary, characters) |
me go goal
The time complexity of the recursive approach to solving this problem is dependent on the number of valid words that can be formed from the given characters and the length of those words.
In the worst case, the time complexity is O(n^m), where n is the number of characters in the characters list and m is the maximum length of the words in the dictionary. This is because the recursive function generates and checks all possible combinations of characters of length up to m, and there are n choices for each character in the combination.
For example, if the dictionary contains all words of length m that can be formed from the characters list, and the characters list has n elements, then the function will generate and check a total of n^m combinations.
On the other hand, if the dictionary is small and the words in the dictionary are short, the time complexity will be much lower. For example, if the dictionary contains only one word of length 1, the time complexity will be O(n).
It’s worth noting that the time complexity of the recursive approach may not be as efficient as the approach provided in the original article, which only needs to check each word in the dictionary individually and does not generate and check all possible combinations of characters.
Approach#3: Using set and subsets
This approach takes a list of words (Dict) and a list of characters (arr) as input. It first creates a set of characters from the input list. Then, it iterates over each word in the dictionary, and checks if the set of characters in that word is a subset of the input set of characters. If it is, then the word is added to the result list. Finally, the function returns the list of words that can be formed using the input characters.
Algorithm
1. Convert the array into a set.
2. Initialize an empty list result to store the possible words.
3. Loop through each word in the given dictionary Dict.
4. Convert the word into a set.
If the set of the word is a subset of the given set arr, append the word to the result list.
5. Return the result list.
Python3
def possible_words(Dict, arr): arr_set = set(arr) result = [] for word in Dict: if set(word).issubset(arr_set): result.append(word) return resultDict = ["go", "bat", "me", "eat", "goal", "boy", "run"]arr = ['e', 'o', 'b', 'a', 'm', 'g', 'l']print(possible_words(Dict, arr)) |
['go', 'me', 'goal']
Time Complexity: O(n*m), where n is the length of the dictionary Dict and m is the length of the longest word in the dictionary. In the worst case, we may have to check all the letters in the longest word in the dictionary against the letters in the given array arr.
Space Complexity: O(m), where m is the length of the longest word in the dictionary. We are using an extra set to store the letters of each word in the dictionary.
