Best explanation again. I think we can optimize Trie search because for each character we are starting search from root of Trie. if we keep last node, we can continue at current position on Trie. If we find a new word or reach leaf, we can reset to root for new search.
Hey! I don't see any advantage of using a Trie, because at any point you will be iterating over all the words and most languages have an indexOf method to see if a word is a prefix of a string. So why do the Trie, the TC is anyway 2^N. We literally gained no improvement in the time by using Trie and not to mention we used additional space. I might be wrong. Here is my implementation in Java. ``` public List wordBreak(String s, List wordDict) { List result = new ArrayList(); wordBreakHelper(s, wordDict, result, new StringBuilder()); return result; } private void wordBreakHelper(String s, List wordDict, List result, StringBuilder current) { if (s.equals("")) { // We do this because we don't want to add space on the last word current.deleteCharAt(current.length() - 1); result.add(current.toString()); return; } for (String word : wordDict) { if (s.indexOf(word) == 0) { current.append(word); current.append(" "); wordBreakHelper(s.substring(word.length(), s.length()), wordDict, result, new StringBuilder(current)); // We do this because we want to remove the last added space and the last word current.delete(current.length() - word.length() - 1, current.length()); } } return; } ```
I was thinking the same, I think when the complete String needs to be matched, Trie is just overkill. Trie is super powerful when there is prefixes and suffixes involved.
Sir you are great teacher , your way to explain complex things in easy ways fantastic. sir please upload more and more problems solution of leetcode please sir.
Hey! This is not related to this question. I got a question in a company's OA and I don't find a solution for it. Can you help? The question is: Given some points of the coordinate plane like (x, y), we need to find the minimum number of straight lines so that all these points get covered. Also, it's similar to LeetCode: 149. I have tried this a lot, can't solve it properly.
@@techdose4u Oh thats nice. I really wanted to join those classes but i already covered alot of the syllabus you mentioned and also i couldn't afford the course. But I'm very happy for you.
@@techdose4u Thank you so much for your prompt reply, and this is an amazing solution. More power to you and your channel for growing and reaching new heights, best wishes!
@@techdose4u Sir, is it possible that even with possible collisions, a Set out performs Trie by big margin as Set is O(1) in average case. I tried solving with both Set and Trie and difference is more than 10 times. (better than 83% using Set and just 12% with Trie)
i stumbled upon this channel , one of my best discoveries of the day !!!!
Love your way of teaching. I was able to code the solution myself even after watching only 7mins of the video
I found your channel a month ago and walkthrough almost all the uploaded videos. Thanks for new uploading!
Great 🔥
You explained problem like you have done PhD in it.
Explained deeply and clearly with every possible concept
Best explanation again. I think we can optimize Trie search because for each character we are starting search from root of Trie. if we keep last node, we can continue at current position on Trie. If we find a new word or reach leaf, we can reset to root for new search.
Yes we can do that
@@techdose4u in python trie is implented using dictionary. If we use that concept TC will be O(len(target)+sum of lengths of worddictionary)
Oh man you're back I can't believe my eyes 😁
I will upload don't worry :)
Hey! I don't see any advantage of using a Trie, because at any point you will be iterating over all the words and most languages have an indexOf method to see if a word is a prefix of a string. So why do the Trie, the TC is anyway 2^N. We literally gained no improvement in the time by using Trie and not to mention we used additional space. I might be wrong. Here is my implementation in Java.
``` public List wordBreak(String s, List wordDict) {
List result = new ArrayList();
wordBreakHelper(s, wordDict, result, new StringBuilder());
return result;
}
private void wordBreakHelper(String s, List wordDict, List result, StringBuilder current) {
if (s.equals("")) {
// We do this because we don't want to add space on the last word
current.deleteCharAt(current.length() - 1);
result.add(current.toString());
return;
}
for (String word : wordDict) {
if (s.indexOf(word) == 0) {
current.append(word);
current.append(" ");
wordBreakHelper(s.substring(word.length(), s.length()), wordDict, result, new StringBuilder(current));
// We do this because we want to remove the last added space and the last word
current.delete(current.length() - word.length() - 1, current.length());
}
}
return;
}
```
I was thinking the same, I think when the complete String needs to be matched, Trie is just overkill. Trie is super powerful when there is prefixes and suffixes involved.
Sir you are great teacher , your way to explain complex things in easy ways fantastic. sir please upload more and more problems solution of leetcode please sir.
Thanks :)
Nice explanation keep on making such videos.....your content is really amazing
Thanks :)
upper one seems little complex - this code worked for me when solved in gfg - class Solution{
public static boolean breakIt(int n ,List al , List dict
, String s ,String ans , int next)
{
// System.out.println(ans+" ---- "+next);
if(s.length()
Happy to see you again sir... ☺😇
:)
After Long time bro. Happy to see you again. Bro can you do some good playlist for system design.
Sure
Hey! This is not related to this question. I got a question in a company's OA and I don't find a solution for it. Can you help? The question is: Given some points of the coordinate plane like (x, y), we need to find the minimum number of straight lines so that all these points get covered. Also, it's similar to LeetCode: 149. I have tried this a lot, can't solve it properly.
149 is about max points on just a straight line. We can repeat the algorithm as long as we don't cover all points. I will try it 👍🏼
Hi bro, please make some tutorial for machine coding rounds and low level design, currently there is no content present on such topics
👍🏼
after a looong time !!!! where were u?
Haha :) Teaching in my LIVE classes :P
@@techdose4u Oh thats nice. I really wanted to join those classes but i already covered alot of the syllabus you mentioned and also i couldn't afford the course. But I'm very happy for you.
How frequently will u upload
Trying for 2 videos per week
@@techdose4u pls do video on leetcode546 it's hard to understand and upload hard problems that covers a lot of concepts
Why is the trie more efficient than map?
Map may have collision :)
TRIE will always find the value in O(string Len) time.
@@techdose4u Thank you so much for your prompt reply, and this is an amazing solution. More power to you and your channel for growing and reaching new heights, best wishes!
@@techdose4u Sir, is it possible that even with possible collisions, a Set out performs Trie by big margin as Set is O(1) in average case. I tried solving with both Set and Trie and difference is more than 10 times. (better than 83% using Set and just 12% with Trie)
where you define ans ?