This was a perfect opportunity for you to teach us the kmp algorithm. Not a lot of good videos on UA-cam 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 :)
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 < len(needle) and r < len(haystack) and haystack[r] == needle[k]: k += 1 r += 1 if k == len(needle): return l return -1 ```
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")
below sol beats 100% percent of the time complexities ,dont know how leetcode determines tc def strStr( haystack ,needle) : l=0 r=len(needle)-1 while r < len(haystack): if haystack[l:r+1] == needle: return l
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?
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.
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
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.
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
"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.
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
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
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
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.
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) < len(needle): 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
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
![Путин и ПЕСКОВ ждут звонка от ТРАМПА 😁 [Пародия]](http://i.ytimg.com/vi/sm8iV0SxRHk/mqdefault.jpg)
Solving this with KMP Algorithm: ua-cam.com/video/JoF0Z7nVSrA/v-deo.html
The second script is much clear than the first one!
This was a perfect opportunity for you to teach us the kmp algorithm. Not a lot of good videos on UA-cam 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 :)
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 < len(needle) and r < len(haystack) and haystack[r] == needle[k]:
k += 1
r += 1
if k == len(needle):
return l
return -1
```
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")
write a condition if(haystick.length() < needle.length() ) then return -1;
below sol beats 100% percent of the time complexities ,dont know how leetcode determines tc
def strStr( haystack ,needle) :
l=0
r=len(needle)-1
while r < len(haystack):
if haystack[l:r+1] == needle:
return l
else:
l=l+1
r=r+1
return -1
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.
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?
Yes I think but substring/splicing is O(n) so time complexity of this algorithm is O(n^2)
Top Top Explanation, Thank You!!!. Please do Leetcode 827. Making a Large Island
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 did nested loop solution, leetcode accepted the solution
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.
Agree, Rabin-Karp is easier to implement and is easier to remember.
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
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.
lass Solution:
def strStr(self, haystack: str, needle: str) -> int:
l,r = haystack.index((needle[0])), haystack.index((needle[0]))
while l
it is correct, it give O((n-m )* m ) TC as per leetcode, but in interviews they might ask to not use string slicing
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.
What is the future of nodejs in jobs and where are more jobs in frontend react or backend nodejs
You should learn Pascal, Elm and AngularJS.
@@Deschuttes lol
Django is the way to go and PyScript is the future 👌
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
"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.
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
why its i: i+ len(needle)? please explain
Why is the complexity of the second solution not O(n)? There is only one for loop.
because calculating the substring and checking it itself takes O(n) time
needlePosition(haystack, needle) {
if (needle === "") return 0
let l = 0
for (let r = needle.length; r < haystack.length; r++) {
const window = haystack.slice(l, r)
if (window === needle) return l
l++
}
return -1
}
Faster right?
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
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
also he has a video of the better ( faster ) implementation of this leetcode problem. using kmp algorithm
man how do you come up with these amazing answers....
How do you start thinking when u see the problems?
thnx man
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
people also need to know about kmp algoriyhm pls do a video on that...Anyways your videos superb as always.
Can anyone explain why is the time complexity O(n+m) and not just O(n)
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.
Thanks
Better In C/C++
Solution does pass on leetcode as of 9/14/23
This won't get you success in an interview. You need KMP algo I guess
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) < len(needle):
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
It's not an good approach at all
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
if needle in haystack:
return haystack.index(needle)
else:
return -1