Solving this with KMP Algorithm: kzread.info/dash/bejne/fKN6krxwnrm5oqQ.html

This was a perfect opportunity for you to teach us the kmp algorithm. Not a lot of good videos on KZread on this topic. If you got this question on an interview and you implemented the KMP algorithm, you would definitely get the job.

Thanks for the excellent explanation! I actually did a nested forloop solution and got the runtime exceeded error and came here to check if I did something wrong! Good to know that it wasn't the case :)

The second script is much clear than the first one!

Just finished my second Exam for Programming 1(Java) at university. This was one of the problems and I had to write out the program by hand.

Top Top Explanation, Thank You!!!. Please do Leetcode 827. Making a Large Island

I think they fixed the time limit issue. I did a nested for loop and it beats 89% in time and 67% in memory with 34ms and 16.2mb. Well, it definitely varies, but stays in the 33ms - 44ms range. ``` class Solution: def strStr(self, haystack: str, needle: str) -> int: for l in range(len(haystack) - len(needle) + 1): if haystack[l] == needle[0]: k = 1 r = l+1 while k k += 1 r += 1 if k == len(needle): return l return -1 ```

if you save the len(string) before entering the loops it wont get TLE. it was getting TLE because for every iteration of i it was calculating len(needle)

why in the leetcode it says that for haystack as hello and the needle as ll , the output should be -1 and not 2 , my code returns 2 but leetcode expects the solution as -1 , why?

I think with the new added case it's not an easy anymore if it needs KMP to be solved without TLE. Anyway, thanks a lot.

I think they might have updated the test cases. With the code at 9:13 it would pass, but with the one at 8:13 (writing string comparsion as an explicit for loop) it would end up with a TLE for the last test case (haystack and needle are something like "aaa.....ab")

@techwithsaket827

Жыл бұрын

write a condition if(haystick.length() < needle.length() ) then return -1;

Can't this problem be done with a fixed sliding window implementation? Wouldn't that give a better run time than the nested for loop approach?

@cobaltumm

4 ай бұрын

Yes I think but substring/splicing is O(n) so time complexity of this algorithm is O(n^2)

Why is the complexity of the second solution not O(n)? There is only one for loop.

Kind of ridiculous that LC times out the first version, the second version is probably only faster because string comparison is implemented in like C. If it were implemented in pure python, I assume it would be slower than the first version because to copy the slice, you always have to iterate through every character in the slice, whereas with the first solution, you can break early.

I came to watch this video hoping to learn KMP algorithm. But i was relieved you mentioned this is not going to be useful to learn when it comes to interviews. submitted my mxn solution at first try so im moving on lol

why its i: i+ len(needle)? please explain

For the KMP fanboys: You do know there are other (even better, according to several research documents I've witnessed) string matching algorithms right? I'd say the best middle ground when in need to string match, is Karp-Rabin. O(n) on average is great and it is way easier to implement if you aren't sharp on the LPS methodology that is needed with implementing KMP.

@staffeng

2 жыл бұрын

Agree, Rabin-Karp is easier to implement and is easier to remember.

man how do you come up with these amazing answers.... How do you start thinking when u see the problems?

lass Solution: def strStr(self, haystack: str, needle: str) -> int: l,r = haystack.index((needle[0])), haystack.index((needle[0])) while l

My friend got asked the KMP algorithm in his Google ML Engineer (L4) Interview. So DON’T ignore it. Times have changed it seems!

thank you

Check this out short and sweet code for the same problem: class Solution: def strStr(self, haystack: str, needle: str) -> int: for i in range(len(haystack)): if needle == haystack[i:i+len(needle)]: return i return -1

Thanks

I used the approach that times out in leetcode in my own interpreter. I plugged in the input that made it time out , and it took at least 5 minutes to give me an answer (index 39,999). I then used the string method .index() and it gave me the same output instantly. How is this so? Does the algorithm behind the built in method not iterate? It seemed to be a constant Time Complexity

@WoWkiddymage

2 жыл бұрын

it's just a much more efficient implementation. Imagine a 100,000 heystack and some long 10,000 long needle with a ton of matching characters, m x n of that is like 1,000,000,000. Obviously built in has a much more rigorous and fast solution to this kind of problem. But I do think they should change the difficulty as it does not really seem "easy" anymore

@WoWkiddymage

2 жыл бұрын

also he has a video of the better ( faster ) implementation of this leetcode problem. using kmp algorithm

What is the future of nodejs in jobs and where are more jobs in frontend react or backend nodejs

@Deschuttes

2 жыл бұрын

You should learn Pascal, Elm and AngularJS.

@izybit

2 жыл бұрын

@@Deschuttes lol

@cont8155

2 жыл бұрын

Django is the way to go and PyScript is the future 👌

people also need to know about kmp algoriyhm pls do a video on that...Anyways your videos superb as always.

Runtime: 36 ms, faster than 80.76% of Python3 online submissions for Implement strStr(). Memory Usage: 13.8 MB, less than 97.14% of Python3 online submissions for Implement strStr(). class Solution: def strStr(self, haystack: str, needle: str) -> int: if needle in haystack: for i in range(len(haystack)): if needle == haystack[i:i+len(needle)]: return i elif needle not in haystack: return -1 else: return 0

@ekcelhenrichekoumelong4457

2 ай бұрын

"needle in haystack:" is already O(n). Which value does it add? In the worst case your Algo is O(n + (n * m)) Which equiv to O(n * m) in therory but still a bit slower in practice. And what's the point of th else block? It will never get called.

Can anyone explain why is the time complexity O(n+m) and not just O(n)

@ekcelhenrichekoumelong4457

2 ай бұрын

Within each loop through the haystack, he loops trough the needle. "haystack[i:len(needle) + i]" is just a syntaxic suggar, under the hood it's like looping through the needle in terms of time complexity.

Solution does pass on leetcode as of 9/14/23

Better In C/C++

Mine got accepted with runtime 11ms and 13.4MB memory code: class Solution(object): def strStr(self, haystack, needle): """ :type haystack: str :type needle: str :rtype: int """ haystack_length = len(haystack) needle_length = len(needle) if len(haystack) return -1 for i in range(0,haystack_length + 1 - needle_length): for j in range(0,needle_length): if haystack[i+j] != needle[j]: break if j == needle_length - 1: return i return -1

This won't get you success in an interview. You need KMP algo I guess

It's not an good approach at all

@MagufoBoy

Жыл бұрын

is basically isSubArray but you return and index instead of a boolean, the most common aproach you will find on the internet use while loops instead of for loops, but is the same logic, just look it up