Great. One suggestion if I may. In your code, the self._search can be a simple list rather than string. Concatenation in Python is quadratic complexity..
This will be inefficient when compared to a Trie approach. The Trie does not grow in size as you have more sentences (it does grow deeper as the sentence length grows). I think overall, the Trie approach is more efficient. The problem limiting the characters to ascii / lowercase is an indication to use Trie.
The implementation is simpler; apart from that, I think they're pretty similar in complexity. I'm not familiar enough with trie implementation to give a deep enough answer!
Hey Tony, I'm confident this approach would be more than enough. It's clean, efficient, and doesn't really contain any redundancies. The trie approach is definitely worth mentioning -- it's also a clean and efficient way to solve the problem. I'd argue that it is harder to implement the trie in the context of the ~30 minutes you might have to answer a question like this, so I highly doubt it would be expected. But, again, mentioning that another method exists and balancing the pros/cons of it is always the way to go :)
@@babybear-hq9yd The time complexity of this is pretty good, but it doesn't scale very well for large datasets, or for large numbers of users. The question on Leet code assumes a single user, and the data provided is really small. In an interview you are unlikely to be asked this exact question, and if you are implementing autocomplete for multiple users you are having to maintain state for each of those users, which is costly. It's also suffers from needing to go to the same place to get the matches for each user, so you can't load balance the requests, and lastly... It assumes that people type a letter at a time, with a trie you can not contact the server until there is a 5ms pause and then request results, with no intermediate search steps. This is a clever solution to the toy problem in the Leet code question, but, I'd be wary of using this in an interview where the problem wasn't worded exactly the same as the Leet code problem.
Great. One suggestion if I may. In your code, the self._search can be a simple list rather than string. Concatenation in Python is quadratic complexity..
Good shout! Pinned this comment :)
it took me 45 minutes to use the trie version of this, and I found yours, I am using this version from now on. Thanks!
love to hear it, glad it helped man!
This will be inefficient when compared to a Trie approach. The Trie does not grow in size as you have more sentences (it does grow deeper as the sentence length grows). I think overall, the Trie approach is more efficient. The problem limiting the characters to ascii / lowercase is an indication to use Trie.
Definitely an alternative solution worth bringing up in your coding interview :)
Great explanation! Thanks :)
Thanks Krishna! Happy to help :)
Whats the time complexity of this algorithm?
check the description
I have a quick question : could you please tell how this solution is better than Trie so that it is possible to argue in the interview?
The implementation is simpler; apart from that, I think they're pretty similar in complexity. I'm not familiar enough with trie implementation to give a deep enough answer!
Do you think interviewers would be looking for you to do the trie approach? Or would this method be okay
Hey Tony, I'm confident this approach would be more than enough. It's clean, efficient, and doesn't really contain any redundancies. The trie approach is definitely worth mentioning -- it's also a clean and efficient way to solve the problem. I'd argue that it is harder to implement the trie in the context of the ~30 minutes you might have to answer a question like this, so I highly doubt it would be expected. But, again, mentioning that another method exists and balancing the pros/cons of it is always the way to go :)
@@babybear-hq9yd The time complexity of this is pretty good, but it doesn't scale very well for large datasets, or for large numbers of users. The question on Leet code assumes a single user, and the data provided is really small. In an interview you are unlikely to be asked this exact question, and if you are implementing autocomplete for multiple users you are having to maintain state for each of those users, which is costly.
It's also suffers from needing to go to the same place to get the matches for each user, so you can't load balance the requests, and lastly... It assumes that people type a letter at a time, with a trie you can not contact the server until there is a 5ms pause and then request results, with no intermediate search steps.
This is a clever solution to the toy problem in the Leet code question, but, I'd be wary of using this in an interview where the problem wasn't worded exactly the same as the Leet code problem.
@@bangequals agreed on wording. if it's a different problem, answer it differently :)