Skip to main content

648. Replace Words


Today's post brings out the awesome question from "problem of the day" on Leetcode. This code implements a solution to replace words in a sentence with their corresponding root words based on a given dictionary of root words. Let's break down the code step by step:



Intuition - So we were provided with the list of words in dictionary and a sentence. For each word in sentence we need to find if that word is starting from any word in the given dictionary. If yes then we need to return that word from dictionary in-place of original word in sentence. 




So it can be either processed using nested loops. one loop on sentence words and inside loop over dictionary words and find out which word in dictionary in the root in word in sentence. For small inputs we can do it but who we are kidding in real life scenario we operate on thousands and sometimes millions of data entries. So check the code constraints and you will realise what i am saying.

Approach- We will optimise the search time by using Tries.

  • Class `Solution`

- `__init__(self)`: Initialises the Solution class with an empty dictionary `self.root` to store the trie structure and an empty dictionary `self.dictionaryDict` to store the dictionary words.


  • Method `createTrie(self, words)`

- `createTrie`: This method creates a trie data structure from the given words. It iterates through each character of each word in the input list `words`, adding each character to the trie. It marks the end of a word by appending `"*"` as a key in the trie.





  • Method `findPrefix(self, words)`

- `findPrefix`: This method finds the shortest prefix of the word in the trie that exists in the dictionary. It starts traversing the trie based on the characters in the input word. If it finds a `"*"` in the trie or reaches a point where the word doesn't exist in the trie, it checks if the current suffix (`suff`) exists in the dictionary. If it does, it returns the current suffix, otherwise, it returns `None`.


  • Method `replaceWords(self, dictionary, sentence)`

- `replaceWords`: This is the main method that replaces words in the given sentence with their corresponding root words from the dictionary. It first initializes an empty list `res` to store the result. Then, it iterates through each word in the dictionary, adding each word to `self.dictionaryDict` and creating a trie for each word using the `createTrie` method. Next, it splits the input sentence into a list of words using `split(' ')`. Then, for each word in the sentence, it finds the shortest prefix using the `findPrefix` method. If a prefix is found, it appends the prefix to the result list `res`, otherwise, it appends the original word. Finally, it joins the elements of `res` with spaces and returns the resulting sentence.



  • Time Complexity

- `createTrie`: Let `n` be the total number of characters in all words in the dictionary. The time complexity of creating the trie is O(n).

- `findPrefix`: Let `m` be the average length of the words in the dictionary and `l` be the length of the longest word. In the worst case, if all words have different prefixes, the time complexity is O(ml).

- `replaceWords`: Let `k` be the number of words in the dictionary and `p` be the number of words in the sentence. The time complexity is O(kml + p).


  • Space Complexity

- The space complexity is O(n + kml), where `n` is the total number of characters in all words in the dictionary, `k` is the number of words in the dictionary, `m` is the average length of the words in the dictionary, and `l` is the length of the longest word.


I hope you like my solution. Do give me an upvote.


Hi, thanks for reading my post, I hope you enjoyed it. So, if you want me to keep you updated with the tech references in coming future please do share your valuable comments with me and also do not forget to share it with your friends....:)
Labels:

Comments

Post a Comment

Popular posts from this blog

1235. Maximum Profit in Job Scheduling

Hi everyone, Today's post is little bit intriguing to me as it took me some time to get t the solution. I have been out of practice for a bit so I was not able to do it in the DP. I didn't want to copy the code. Though i understood the code after i checked its solution in the discussions. Anyways, i tried to do it with heap and with some thinking I was able to do it and with my surprise It performed real well. I would like to jump to the solution but first I would like to explain a little bit about heaps so you can get better understanding of the code. A heap is like a special type of list where the smallest (or largest) item is always at the front. Think of it like a priority line at a theme park, where the person with the highest priority goes to the front. There are two types of heaps: Min Heap: The smallest item is at the front. It's like standing in a line where the shortest person is always at the front. Max Heap: The largest item is at the front. It's like stand
2 comments
Read more

1456, Maximum Number of Vowels in a Substring of Given Length

Hi, folks today I am here with an interesting coding problem from Leetcode. *To directly go to the question please click here. So I will walk through the solution. It will be a brute force and an optimized way solution. I will be explaining the optimized way solutions in depth. # Intuition For any substring of length k, we need to find how many vowels are there in it and provide the highest count of all counts of vowels in a substring. Test Case 1 Input k = 2 and s='asjdee' Output - 2 Explanation: As for substring of length k=2, in the string 's' we have 'ee' when the length is k and the vowels count is 2 Test Case 2 Input k=3 and s='aasdiisdwe' Output - 2 Explanation - For all the substrings with length k = 3 we have 'aas' and 'dii' with 2 vowels each in it. Brute Force - Looping (twice) - Gives TLE (Not recommended) # Approach Create a hashmap (dictionary) with all the vowels in it. Loop through the string till len(s)-k element of strin
Post a Comment
Read more

1287. Element Appearing More Than 25% In Sorted Array

Hi, Today i bring you new Leetcode problem. Its an easy one :) The problem is - Element Appearing More Than 25% In Sorted Array As qs. explains itself we need to find a number that appears 25% times or more than the length of he array. So for example if array has length of 8 then the resultant number should appear 2 or more times. The constraints given are - 1 <= arr.length <= 100, 0 <= arr[i] <= 10 5 So, lets look at the cases which we may encounter. 1. if length is 1. then the number itself is the result. 2. if length is divisibe by 4 3. if length is not divisible by 4. Let's look at the code now...  class Solution : def findSpecialInteger ( self , arr : List[ int ]) -> int : n = len (arr) start = 0 end = n hm = defaultdict() for i in arr: hm[i] = hm.get(i, 0 )+ 1 for i in hm: if hm[i]>n// 4 : return i Now we will go through the code. Step 1: Initializatio
Post a Comment
Read more