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
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
Lovely
Amazing effort. Keep it up.
Great solution video! Request to solve Leetcode Problem 4. Median of Two Sorted Arrays if possible, thank you!
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
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
How to watch the hidden videos?