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

[@NeetCode]

Solving this with KMP Algorithm: kzbin.info/www/bejne/gKCpYY1to7uGqKM

[@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 KZbin on this topic. If you got this question on an interview and you implemented the KMP algorithm, you would definitely get the job.

[@yunaf4609]

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

[@akashgeorge5433]

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

[@yixie3834]

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;

[@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)

[@ahmadahmed6746]

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

[@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.

[@inno6123]

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

[@abdelkrimyahiaoui6777]

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]

"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.

[@bashaarshah2974]

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]

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

[@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.

[@staffeng]

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

[@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.

[@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

[@kumaravelpalanisamy3962]

I did nested loop solution, leetcode accepted the solution

[@ZhenkarGowdaKP]

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

[@nilsh5027]

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.

[@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?

[@itsthemeg]

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

[@akashgeorge5433]

it is correct, it give O((n-m )* m ) TC as per leetcode, but in interviews they might ask to not use string slicing

[@himanshugupta7647]

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

[@Deschuttes]

You should learn Pascal, Elm and AngularJS.

[@izybit]

@@Deschuttes lol

[@cont8155]

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

[@CodyWakeford]

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?

[@adityawagh]

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

[@parantikaghosh4396]

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

[@illuminati7670]

because calculating the substring and checking it itself takes O(n) time

[@ianbilello4997]

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]

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]

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

[@aakansha7256]

thnx man

[@akashdey5637]

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

[@sanooosai]

thank you

[@yogeshgupta6094]

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

[@naimeimran3247]

Thanks

[@akhiluthappa]

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

[@ekcelhenrichekoumelong4457]

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.

[@__hannibaalbarca__]

Better In C/C++

[@defnotava2407]

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

[@MandolinSashaank]

if needle in haystack: return haystack.index(needle) else: return -1

[@angelwidatti]

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

[@AsifIqbalR]

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

[@bhavyajindal9678]

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