In this article, we will code a python program to create a dictionary with the key as the first character and value as words starting with that character.
Dictionary in Python is an unordered collection of data values, used to store data values like a map, which unlike other Data Types that hold only a single value as an element, Dictionary holds the key: value pair. Key-value is provided in the dictionary to make it more optimized.
Examples:
Input: Hello World
Output: {'H': ['Hello'],
'W': ['World']}
Input: Welcome to GeeksForGeeks
Output: {'W': ['Welcome'],
't': ['to'],
'G': ['GeeksForGeeks']}
Approach:
- We will save the string in a variable and declare an empty dictionary.
- Then we will split the string into words and form a list of those words.
- For each word, we will check if the key for that word is present or not.
- If it is not then we will add that key and word to the dictionary and if it is already present then we will append that word to that key’s sublist.
Below is the implementation of the above approach:
Python3
# Python program to Create a Dictionary with Key as First# Character and Value as Words Starting with that Character# Driver Code# Declaring String Datastring_input = '''Lazyroar is a Computer Science portal for Lazyroar. It contains well written, well thought and well explained computer science and programming articles, quizzes etc.'''# Storing words in the input as a listwords = string_input.split()# Declaring empty dictionarydictionary = {}for word in words: # If key is not present in the dictionary then we # will add the key and word to the dictionary. if (word[0] not in dictionary.keys()): # Creating a sublist to store words with same # key value and adding it to the list. dictionary[word[0]] = [] dictionary[word[0]].append(word) # If key is present then checking for the word else: # If word is not present in the sublist then # adding it to the sublist of the proper key # value if (word not in dictionary[word[0]]): dictionary[word[0]].append(word)# Printing the dictionaryprint(dictionary) |
{'G': ['Lazyroar'], 'i': ['is'], 'a': ['a', 'and', 'articles,'], 'C': ['Computer'], 'S': ['Science'], 'p': ['portal', 'programming'], 'f': ['for'], 'g': ['Lazyroar.'], 'I': ['It'], 'c': ['contains', 'computer'], 'w': ['well', 'written,'], 't': ['thought'], 'e': ['explained', 'etc.'], 's': ['science'], 'q': ['quizzes']}
Time complexity: O(n), where n is the total number of characters in the input string.
Auxiliary space: O(k * n), where k is the number of unique keys (i.e., the number of unique first characters of words) and n is the total number of words in the input string.
You can see that in the above program’s output the words starting with G have two keys ‘G‘ and ‘g‘ so to remove that issue and make the code case-insensitive we will make use of the lower() function in python. We will save all keys with the lower case so that whenever we will check for the key both the words starting with ‘G‘ and ‘g‘ both will come under the same key. Below is the implementation:
Python3
# Python program to Create a Dictionary with Key as First# Character and Value as Words Starting with that Character# Driver Code# Declaring String Datastring_input = '''Lazyroar is a Computer Science portal for Lazyroar. It contains well written, well thought and well explained computer science and programming articles, quizzes etc.'''# Storing words in the input as a listwords = string_input.split()# Declaring empty dictionarydictionary = {}for word in words: # If key is not present in the dictionary then we # will add the key and word to the dictionary. if (word[0].lower() not in dictionary.keys()): # Creating a sublist to store words with same # key value and adding it to the list. dictionary[word[0].lower()] = [] dictionary[word[0].lower()].append(word) # If key is present then checking for the word else: # If word is not present in the sublist then # adding it to the sublist of the proper key # value if (word not in dictionary[word[0].lower()]): dictionary[word[0].lower()].append(word)# Printing the dictionaryprint(dictionary) |
{'g': ['Lazyroar', 'Lazyroar.'], 'i': ['is', 'It'], 'a': ['a', 'and', 'articles,'], 'c': ['Computer', 'contains', 'computer'], 's': ['Science', 'science'], 'p': ['portal', 'programming'], 'f': ['for'], 'w': ['well', 'written,'], 't': ['thought'], 'e': ['explained', 'etc.'], 'q': ['quizzes']}
Time complexity: O(n), where n is the total number of characters in the input string.
Auxiliary space: O(k * n), where k is the number of unique keys (i.e., the number of unique first characters of words) and n is the total number of words in the input string.
METHOD 3:Using itertools
APPROACH:
The program takes an input string, splits it into words and creates a dictionary with the first letter of each word as the key and the corresponding word(s) as the value(s) in a list. This is done using the itertools.groupby() function and a lambda function to sort and group the words by their first letter.
ALGORITHM:
1. Split the input string into words and store them in a list.
2. Create an empty dictionary to store the result.
3. Use itertools.groupby() function to group the words by their first letter.
4. sort the words before grouping.
5. Use a lambda function to extract the first letter of each word for grouping.
6. Store the first letter as the key in the result dictionary and the corresponding word(s) as the value(s) in a list.
7. Print the result dictionary.
Python3
import itertoolsinput_str = 'Hello World'words = input_str.split()result = {}for key, group in itertools.groupby(sorted(words), key=lambda x: x[0]): result[key] = list(group) print(result) |
{'H': ['Hello'], 'W': ['World']}
Time Complexity:
The time complexity of this program depends on the length of the input string and the number of words in it. The program has to sort and group the words, which takes O(n log n) time, where n is the number of words in the input string. The dictionary creation takes O(n) time, where n is the number of groups. Therefore, the overall time complexity of the program is O(n log n).
Space Complexity:
The space complexity of the program depends on the length of the input string and the number of unique keys in the result dictionary. The program creates a list to store the words and a dictionary to store the result. The size of the list is proportional to the number of words in the input string, and the size of the dictionary is proportional to the number of unique keys. Therefore, the overall space complexity of the program is O(n), where n is the length of the input string.
