Find the Index of the First Occurrence in a String

[@duttulurihitheshkumar4800]

Great solution video! Request to solve Leetcode Problem 4. Median of Two Sorted Arrays if possible, thank you!

[@deepakjyoti8355]

Amazing effort. Keep it up.

[@jst8922]

Using the Knuth-Morris-Pratt (KMP) algorithm, which is very efficient for large texts and patterns. The KMP algorithm works in O(m + n) time complexity, where: m is the length of the needle n is the length of the haystack class Solution: def strStr(self, haystack: str, needle: str) -> int: # Step 1: Edge case, if needle is empty, return 0 as per problem statement if len(needle) == 0: return 0 # Step 2: Build the LPS array for the needle def build_lps(needle: str) -> list: lps = [0] * len(needle) # LPS array of the same length as needle length = 0 # Length of the previous longest prefix suffix i = 1 while i < len(needle): if needle[i] == needle[length]: length += 1 lps[i] = length i += 1 else: if length != 0: length = lps[length - 1] # Try the previous longest prefix suffix else: lps[i] = 0 i += 1 return lps # Step 3: Use the LPS array to search for the needle in the haystack lps = build_lps(needle) i = 0 # index for haystack j = 0 # index for needle while i < len(haystack): if haystack[i] == needle[j]: i += 1 j += 1 if j == len(needle): return i - j # Match found, return the start index elif i < len(haystack) and haystack[i] != needle[j]: if j != 0: j = lps[j - 1] # Skip to the next possible match in the needle else: i += 1 # No match found, move to the next character in haystack return -1 # Needle not found in haystack

[@jst8922]

Regarding: LPS Array Construction here is an example Input: haystack = "sadbutsad", needle = "sad" For the needle = "sad": Let's construct the LPS array step by step: First, we create an LPS array of the same length as the pattern (needle) Length of "sad" = 3, so LPS array size = 3 LPS array construction rules: LPS[0] is always 0 For other positions, we find the longest proper prefix which is also a suffix Let's build it: Pattern: s a d Index: 0 1 2 LPS: 0 0 0 Step-by-step process: i = 0: LPS[0] = 0 (always) i = 1: Compare 's' and 'a' They don't match LPS[1] = 0 i = 2: Compare 's' and 'd' They don't match LPS[2] = 0 Final LPS array: [0, 0, 0] another example: Input: haystack = "sadbutsad", needle = "sade" Let's construct the LPS array step by step: First, create an LPS array of the same length as the pattern (needle) Length of "sade" = 4, so LPS array size = 4 LPS array construction rules: LPS[0] is always 0 For other positions, find the longest proper prefix which is also a suffix Pattern: s a d e Index: 0 1 2 3 LPS: 0 0 0 0 Step-by-step process: i = 0: LPS[0] = 0 (always) i = 1: Compare 's' and 'a' They don't match LPS[1] = 0 i = 2: Compare 's' and 'd' They don't match LPS[2] = 0 i = 3: Compare 's' and 'e' They don't match LPS[3] = 0 haystack: s a d b u t s a d needle: s a d e LPS: 0 0 0 0 Step 1: Match 's' at i=0 Step 2: Match 'a' at i=1 Step 3: Match 'd' at i=2 Step 4: Mismatch at i=3 ('b' ≠ 'e') - Use LPS to shift pattern - j = lps[2] = 0 Step 5: Start matching from beginning of needle Step 6: Continue until end of haystack

[@saikumarkotha723]

How to watch the hidden videos?