Knuth-Morris-Pratt KMP - Find the Index of the First Occurrence in a String - Leetcode 28 - Python
Vložit
- čas přidán 27. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
CODE ON GITHUB: github.com/neetcode-gh/leetco...
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: leetcode.com/problems/impleme...
0:00 - Read the problem
1:00 - Review Brute Force O(n * m)
3:45 - Motivation for KMP
5:25 - Understanding LPS
9:15 - Coding LPS
26:35 - Coding KMP
leetcode 28
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#kmp #knuth-morris-pratt #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Code on Github: github.com/neetcode-gh/leetcode/blob/main/28-Implement-strStr.py
I recommend using the timestamps and watching this at 1.5x Speed, at least the LPS portion, which turned out longer than I expected.
no that was perfect for guys like me thank you very much
Why cant we use in built stl function
String.find(substring)
To locate the index of string ?
@@ary_21 because this will only return the first occurence of the substring. Morever, the "substring" function internelly works in O(n) time. So the totall complexity would be O(n^2), where the optimal approch has O(n) time. And that's very bad. And also if you want to count the number of occurences of the substring, the "stl function" approach will definitely give you TLE. :)
@@xerOnn35
Got it 👍
Thanks !
Thank you for acknowledging how complex this algo is. I thought i was crazy for struggling so much. Finally understand it, somewhat :'). Thanks for making this
exactly. i came back after leaving this algo and did not understand what I wrote at all and I thought I was just being stupid lol
If someone says they can explain KMP better, they are lying. It doesn't get any better than what you just did. Amazing Neetcode. 🙏
0:35 - Yes, I too would describe independently re-discovering a complex search algorithm during an interview as "very very hard"
lmao, as soon as I submitted his first solution (m * n) doing it myself and it exceeded time I realized this wasn't going to be an "easy" problem :') . WTH is this leetcode.
@@WoWkiddymage
To be honest trying the same problem with rabin karps algorithm is very easy.
If given the hint "each sliding window can have a unique signature" you can yourself re-discover the algo even if not read of before.
Kmp , booyre moore , rabin karp are all linear algorithms
Especially considering it took 3 guys to initially discover it!
@@WoWkiddymage well I wrote a brute force (mentioned below, which got accepted btw) but the code was so ugly, I knew for sure there exists an optimal solution and here I am.
bool rotateString(string s, string goal) {
int n = s.size();
for(int i=0; i
I saw many explanations on kmp algo, but the explanation you provided is the best and the easiest to understand, kudos to you !
I wish this video came around sooner. Was asked a similar question during a Microsoft interview two weeks ago. The interviewer expected me to come up or remember KMP lol. But thank you NC! Please keep up the good works!
The best online KMP algorithm explanation! Thank you Sir!
Please try to make future solution videos in this dual screen format. It’s really helpful to visualize the intuition behind each line of code in real time.
Yeah
One of the greatest explanations Neel. It's really very helpful and let me tell you I have seen it more than 4 times and now I know how it works. Thanks, man.
We asked for it in the previous video and you made a video on it, thanks!
Exactly, I literally put a comment on his last video. What a legend
This is the best KMP solution I've been seen, very clear, thank you!
Thank you for your hard work ! Video is incredibly useful and easy to understand.
This is the best explaination video for KMP algorithm!! I find that explaining code parallely is very helpful for this algorithm. Thank you for your efforts!!
At 22:00 I think I really started getting it!
Thanks Neetcode for the clear explanations as usual.
Thanks Mr.Neet for listening.
This is one of the best explanations to the KMP algorithm, thank you :)
That is super helpful. I finally understand this, two days
Beautiful explanation, only the one who understands the logic can explain others with such clarity
This is really a great attempt at trying to explain the KMP and somewhat some intuition behind why it works! Really a very complicated and non-intuitive algorithm but brilliantly explained here.
u make it so easy and understandable . ig this is the best video on kmp i came across.
Awesome work, ! thank u for putting in so much effort and thanks to me also for making 1/5th effort to make it to the end of this video. good to see that u covered so many test cases, which made the explanation more clear.
Honestly, This was the best explanation I have found on the internet, and trust me I have watched a hell lot smfhhh
Thanks NeetCode, it's pretty hard to find a good explanation on the KMP algorithm and you did a great job of explaining it here. Would it be possible for you to cover the Aho Corasick algorithm at some point? I'm finding it difficult to find a good resource explaining that one and having a NeetCode explained version would be a nice follow up to this one as I believe Aho Corasick uses KMP to efficiently find substrings in strings along with Tries.
This is the first video from NeetCode that I can't seem to understand wow! speaks to the complexity of the algo or maybe I am just mediocre XD
It's amazing how stuff like this is actually free. Thanks dude!
Thank you for this amazing video!
Finally, I understood this algorithm.
Wow. You listened to the feedback from viewers. Goddamn legend ✌
Best kmp explanation i've ever found on youtube!!!
Excellent attention to feedback
Enormous thanks for making this video!
What a great explanation. Thanks!!!!!!
You saying again and again it's tough and really it's. But you make the algorithm very easy by your explanation. Superb work....
Best KMP algo explanation ever. Thanks neetcode.
Finally understood this KMP in my 6years of studies. Theenks.💪🏼
Clean and precise, thanks @NeetCode
Hats off to your effort. 👍🏻
Very well explained thank you so much
why do u sound like you're explaining it to me for the fifth time
Very detailed explanation.Thank you very much
Very helpful, thank you!
Simply beautiful explanation. Very near perfect one.
Great work. Keep it up :-)
Appreciate Your hard work. It was hard. I will need to review again a few times to figure out and remember.
Great explanation! Thank you so much
this is the best video on youtube for this question
Thanks for the amazing explanation!
Sir pls take questions from the previous week's contest. They were too odd and problem statement were not put up correctly. Thanks 😊
Tysm! I would have never understood this if I tried learning on my own.
Thanks Man!Saved mine time❤
Great explanation! 👍
this was so helpful!! thank u!!
Best explanation! Thanks so much
So totally helpful! Thanks!
Good stuff Sir ☺️
best explanation on KMP on yt ❤
Best explaination I found for KMP thanks
Thanks for this
One of the best explanation out there for this hard hard hard algorithm
Awesome explanation!
Yeah true, that's one of your longest videos but you explained KMP-algorithm very clearly
Great explanation.
Could you also cover Rabin Karp's algorithm for the same leetcode problem?
Amazing video and explanation.
first time in neetcode history* bro made it wild
@NeetCode Please correct me if I'm wrong, but on 19:12, when you say "that's what the 1 tells us..", i think you meant to circle the 1st and the 2nd "A" in the text and not the 1st and 3rd "A".
Loved this video!
Thank you for the video.
this was really helpful thanks
Great Explanation 🙌🙌🙌🙌
That just went through my brain. thanks
prevlps is the value stored or the pointer to that location?
Thank you so much!
I did this yesterday on leetcode. After solving it turnns out to be KMP algorithm.
Can someone tell the difference between LPS and DFA (Deterministic finite automaton) in the context of the algorithm?
I do not understand the tricky part when building the LPS array, when i and j do not match, why move j by the VPS[i - 1]? Because move that way you will skip some middle elements. Is there a proof that garentee the longest prefix suffix?
yew, i also want answer for this logic
Incredible explanation! Thanks for the video.
bro i got google screening interview in few days - i remember u said in one of the videos that you can find the screening question online, but i dont see it. although i have prepared from leetcode. But i remember u said the question are easy, it not that easy also, its all good medium level problems
cant we use rabin karp algorithm it also takes o(|n| +|m|) right?
If prevLPS come backs to prevLPS=0 then it can further move max n-i steps ,that's why time complexity is O(N)
You always explain such this it is one of the best explanation🤩
I was asked this for FAANG interview
I don't understand why we use prevLps as an index , but set the value from lps[prevLps - 1]; Why value can be used as index?
hey Neetcode at timestamp 22:40, why was LPS[6]!= 6? because for the substring 'AAACAAA' -> prefix(AAACAA)==suffix('AAACAA') and that length is 6. please tell me if i am mistaken.
thanks! it's helpful
thank you sir!
I dont understand why prevLPS = lps[prevLPS - 1]? is that always right?
you are awesome, thank you
Hey guys, I have a question regarding the calculation of the LPS array. When it comes to the "else" condition, why do we let prevLPS = LPS[prevLPS-1] instead of decrementing prevLPS by 1? 🤔 THANKS.
I was wondering the same thing
If you found an explanation please share
@@prakhargupta4320 checj for other strings as well youy will get it
thank you very much
very helpful video
24:10 I wonder why here we can say LPS[2]'s value means the first two chars match the 5th,6th chars. In my view when the LPS[2] is determined, we don't know the following matches, so its value can only tell the first two match the 1th,2th two (matching prefix-suffix numbers up to current bit). Since then LPS[2] haven't change, why has the meaning changed? Thank you the same.
Thanks a lot.
am I correct that these algorithm does not work correct for such case
string haystack ("ababcaababcaabc");
string needle ("ababcaabc");
By the end of the video it looks like if you saved the X, the pointer of the needle would need to go back again. If I am not wrong, worst case is O(n*m) like rabin karp, as if the needle is AAAA and the hays is like AAAX copied many many times, it always will go back to the start of LPS array. Thus, O(n*m)
Can you do Leetcode 30 video? I wander how can we implement KMP in it
Best explanation
Tbh if you wrap your head around the working of the KMP algo, it’s not that complicated and pretty astonishing what it achieves
Not me legitimately saying "wow" when you went dual screen mode 😭
＠23:34 “C“ is at index three, not index four; 0, 1, 2, 3…
at 24:28 you said that that we would take lps[prevLPS] and add 1 to it but in the code in first condition you wrote lps[i]=prevLPS+1 and not lps[prevLPS] +1