For the problem "Design Add and Search Words Data Structure", I have wrote the following naive approach, which somewhat feels wrong or not properly written. But this is as far as I know about hashing and using hash maps in Python.
Can you highlight a few points regarding my solution? What should I improve in the following approach:
"The problem statement asks us to devise an algorithm to support the three mentioned functionalities. One possible approach is to utilize a hash map. We can start by creating an empty hash map and gradually adding words with identical lengths as values under the corresponding key. When searching for a word in the hash map, we can look for the length of the word as the key and then verify if each letter of the word precisely matches the stored word associated with that key in the hash map.
The time taken to add a word in the hash map is O(m), where m is the length of the word. The search time complexity for this approach would be O(n × m), where n is the number of words. However, this solution would be inefficient when searching for all strings with a common prefix.
Furthermore, once the size of the hash map increases, there will be increased hash collisions, degrading the time complexity to O(n^2 × m)."
From what I've come to know is that:
If a key does not exist in the hash map and has not been cached, then the average time would be O(L).
If a key does not exist in the hash map but it has been cached, then the average time would be O(1).
Overall the time taken to confirm whether the key is present in the hash map is O(l).
Since Python defaultdict is a hash map, so in the worst case, the time complexity is O(n), only when the hash function is written badly and results in a lot of collisions. Although this is quite rare, so the average time complexity in Python is O(1).
Am I correct on this? Based on all these points, what should be the naive approach now? How will it affect my time complexity for the addition and searching operation.