Python – Test for Word construction from character list

Given a List and a String, test if the string can be made from list characters.

Examples:

Input : test_list = ['g', 'g', 'e', 'k', 's', '4', 'g', 'g', 'e', 's', 'e', 'e', '4', 'k'], 
                    test_str = 'neveropen4neveropen' 
Output : True 
Explanation : String can be made according to character frequencies.

Input : test_list = ['s', '4', 'g', 'g', 'e', 's', 'e', 'e', '4', 'k'], test_str = 'neveropen4neveropen' 
Output : False 
Explanation : String cannot be made according to character frequencies. 

Method #1: Using all() + count()

In this, we test for all characters count from the string to be less than the frequency of each character in the list. The frequencies are extracted using the count() function. 

The original list is : ['g', 'g', 'e', 'k', 's', '4', 'g', 'g', 'e', 's', 'e', 'e', '4', 'k']
Is word construction possible ? : True

Time Complexity: O(n)
Auxiliary Space: O(1)

Method #2 : Using Counter()

In this, we compute frequencies using Counter(), and then perform subtraction of words from list characters. In the case of an empty list, means not possible to form a word.

The original list is : ['g', 'g', 'e', 'k', 's', '4', 'g', 'g', 'e', 's', 'e', 'e', '4', 'k']
Is word construction possible ? : True

Time Complexity: O(n)
Auxiliary Space: O(1)

Method #3: Using re

1. Using the re module to check if all the characters in the test string are present in the test list in a single line.
2. The code first concatenates the elements of the test list into a single string. Then, the re.search() function is used to search for a match of the test string with a regular expression pattern that consists of only the characters from the concatenated string. 
3. If the match is found, the re.search() function returns a Match object, which is truthy, and the result will be True. 
4. If the match is not found, the function returns None, which is false, and the result will be False.

Is word construction possible? : True

Time Complexity: O(n)
Auxiliary Space: O(1)

Method #4: Using a dictionary

1. Initialize an empty dictionary named char_freq.
2. Iterate through each character in the test_list.
3. For each character, if it already exists in the char_freq dictionary, increment its frequency count.
4. Otherwise, add it to the dictionary with a frequency of 1.
5. Iterate through each character in the test_str.
6. For each character, if it exists in the char_freq dictionary and its frequency count is greater than 0, decrement its frequency count. Otherwise, the word cannot be constructed from the test_list.
7. If all characters in the test_str have been successfully checked, return True to indicate that the word can be constructed from the test_list. Otherwise, return False.
8. The time complexity of this method is O(n), where n is the length of the test_list or test_str. The auxiliary space complexity is also O(n), where n is the number of unique characters in the test_list

Example:

The original list is : ['g', 'g', 'e', 'k', 's', '4', 'g', 'g', 'e', 's', 'e', 'e', '4', 'k']
Is word construction possible ? : True

Time complexity: O(n), where n is the length of the test_list or test_str. 
Auxiliary space: O(n), where n is the number of unique characters in the test_list.

Method #5 : Using operator.countOf() method

Approach:

1. Remove duplicates from string test_str and store in x using list(),set() methods,set a variable c=0
2. Check whether count of elements in test_list is greater than or equal to the count of elements in test_str, if yes increment c by 1(using operator.countOf())
3. If c is equal to the length of x then the given string test_str can be formed from test_list, set res to True.
4. Else set res to False.
5. Print boolean true or false based on whether the word can be made from the input. 

The original list is : ['g', 'g', 'e', 'k', 's', '4', 'g', 'g', 'e', 's', 'e', 'e', '4', 'k']
Is word construction possible ? : True

Time Complexity : O(N) N – length of x
Auxiliary Space: O(1) Since we are using a single variable result.