Find the Index of the First Occurrence in a String - Leetcode 28 - Python

0:00 - Read the problem
1:35 - Drawing Explanation
3:40 - Coding Explanation

leetcode 28

#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[hsoley]

The second script is much clear than the first one!

[CEOofTheHood]

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

[yunaf]

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 :)

[aisteelmemesforaliving]

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
```

[ahmadahmed]

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

[Kashiskthakur]

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)

[yixie]

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

[bashaarshah]

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?

[criostasis]

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.

[mnm__studios]

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

while l<=r:
if haystack[l:r+1] == needle:
return l
else:
l+=1
r+=1
return -1

Is this algorithm correct as well?

[ovqmvdf]

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

[valkon_]

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.

[inno]

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

[nilsh]

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.

[kshithijiyer]

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

[kumaravelpalanisamy]

I did nested loop solution, leetcode accepted the solution

[avih]

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.

[abdelkrimyahiaoui]

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

[himanshugupta]

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

[sharmaakshat]

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?