Thanks, really appreciate the video, though I am just starting to learn these concepts, the thought process was good to know, going to checkout the playlists in the description :)
also if we use hash as: ap^3 + bp^2 + cp + d (for string "abcd" and base p) then we don't have to use inverse powers doesn't mean much but skips inverse modulo use
Hi Bro, really good content. intuition is clear. I first tried submitting my code similar to yours 1st approach( using hashing ) but got wrong answer at 799/807. After that I submitted your code and faced the same issue. can you pls look into this.
They might have updated the test case to introduce collision for the specific hash function we are using. You can just duplicate the hash calculation with different values of P and/or MOD and compare as a pair instead of single value to avoid collision.
To be honest, if you are able to reach 799 test cases through your code, you probably understand everything that this approach would teach you and simply move forward to different approach :)
class Solution { HashMap map=new HashMap(); class TrieNode { TrieNode[] children; boolean isEndOfWord; public TrieNode() { children = new TrieNode[26]; isEndOfWord = false; } }
public void insert(String word, TrieNode root) { TrieNode node = root; for (char c : word.toCharArray()) { int index = c - 'a'; if (node.children[index] == null) { node.children[index] = new TrieNode(); } node = node.children[index]; } node.isEndOfWord = true;
}
public boolean findWordsWithPrefix(String prefix, TrieNode root) { TrieNode node = root; int result=0; for (char c : prefix.toCharArray()) { int index = c - 'a'; if (node.children[index] == null) { return false; // No match for the prefix } else result++; node = node.children[index]; } return true; }
public int find(String s, TrieNode root, HashMap memo, int index, int n){ // System.out.println(s); // int n1=s.length(); if(index==n) return 0; if(memo.containsKey(index)) return memo.get(index); boolean found=false; int x=10000000; String temp=""; for(int i=index;i
if(map.containsKey(temp)) cnt=map.get(temp); else { cnt=findWordsWithPrefix(temp, root); map.put(temp, cnt); } Why are you creating a temporary string and the searching it in a hashmap. Why not simply iterate over the trie and let trie do the work? Something like - tmp_root = root for(int i=index;i
Superb Explanation as always.These days I look for your explanation videos in every leetcode contest 4th problems
good explanation, good pace.
Great explaination ❤. The z function approach is really understandable .
bro, I've subscribed, keep doing what you are doing, your channel is literally underrated.
Your explanation is really impressive. The ideas and observations you put at every step.. its just the evidence of how a problem should be approached.
Thanks, really appreciate the video, though I am just starting to learn these concepts, the thought process was good to know,
going to checkout the playlists in the description :)
Great Solution...
we can also precompute a rolling hash using rabin karp algorithm instead of building trie time complexity will remain the same..
Yes that would work too.
you earned a subscriber today, great great work
preparing for uber, want to give any tips, suggestions
also if we use hash as: ap^3 + bp^2 + cp + d (for string "abcd" and base p) then we don't have to use inverse powers
doesn't mean much but skips inverse modulo use
Please try to upload yesterday biweekly contest 3rd problem 🙏
Here you go - ruclips.net/video/ea9Kjfc9ZzI/видео.html
@@codingmohan Thanks a lot 😭
Can you explain about the seg tree why minimum?
getting tle with the approach of 3 problem using recursion + memo+trie, please look into my solution
Hope this is resolved now?
Hi Bro, really good content. intuition is clear. I first tried submitting my code similar to yours 1st approach( using hashing ) but got wrong answer at 799/807. After that I submitted your code and faced the same issue. can you pls look into this.
They might have updated the test case to introduce collision for the specific hash function we are using.
You can just duplicate the hash calculation with different values of P and/or MOD and compare as a pair instead of single value to avoid collision.
To be honest, if you are able to reach 799 test cases through your code, you probably understand everything that this approach would teach you and simply move forward to different approach :)
Still getting TLE. 916/929 :((((
Replied to the other comment. Let me know if you are still facing issues.
class Solution {
HashMap map=new HashMap();
class TrieNode {
TrieNode[] children;
boolean isEndOfWord;
public TrieNode() {
children = new TrieNode[26];
isEndOfWord = false;
}
}
public void insert(String word, TrieNode root) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEndOfWord = true;
}
public boolean findWordsWithPrefix(String prefix, TrieNode root) {
TrieNode node = root;
int result=0;
for (char c : prefix.toCharArray()) {
int index = c - 'a';
if (node.children[index] == null) {
return false; // No match for the prefix
}
else result++;
node = node.children[index];
}
return true;
}
public int find(String s, TrieNode root, HashMap memo, int index, int n){
// System.out.println(s);
// int n1=s.length();
if(index==n) return 0;
if(memo.containsKey(index)) return memo.get(index);
boolean found=false;
int x=10000000;
String temp="";
for(int i=index;i
if(map.containsKey(temp))
cnt=map.get(temp);
else {
cnt=findWordsWithPrefix(temp, root);
map.put(temp, cnt);
}
Why are you creating a temporary string and the searching it in a hashmap. Why not simply iterate over the trie and let trie do the work? Something like -
tmp_root = root
for(int i=index;i
Java's HashMap is too slow, apart from above optimization use array for dp and trie.
@@codingmohan thanks, i got u.