0028. Implement strStr()

Easy | String + KMP | 12 ms (97.47%), 13.5 MB (99.75%)

❓ Problem Statement

Source: LeetCode - Implement strStr() GitHub: Solution / Performance

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

✍🏻 Constraints & Example

💡 Ideas

It's quite straightforward to iterate through the input string (haystack) and check whether the target string (needle) is part of it or not.

Instead, let's use the KMP algorithm to solve this problem.

For using KMP, we first create the LPS (Longest proper Prefix also Suffix) table. Then we use the same algorithm that creates the LPS table but with few tweaks with the LPS table as a reference to find the answer.

• To create an LPS table, we use two pointers to iterate the target string (needle). One for iterating moveP = 0 Second for pointing to the previous same char by jumping jumpP = 1

  • If two chars are the same (pointed by moveP and jumpP respectively) Mark the table by table[moveP] = jumpP + 1 and move both pointers by increasing their index.

  • If two chars are not the same

    • If jumpP == 0 , it means that we cannot jump further. Set table[moveP] = 0 and moveP += 1

    • Otherwise, we jump by jump = LPSTable[jumpP - 1]

• After we have the LPS table, we use the same algorithm with few tweaks

  • moveP, jumpP = 0, 0

  • Compare between two strings by haystack[moveP], needle[jumpP]

  • For jumping jumpP = LPSTable[jumpP - 1]

  • Return condition If jumpP == len(needle), return moveP - len(needle)

🤖 Python3

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # (base case)
        if not needle: return 0
        if not haystack: return -1
        if len(needle) > len(haystack): return -1
        
        # ==================================================
        #  String + Two Pointer                            =
        # ==================================================
        # n = length of haystack
        # m = length of needls
        # time  : O(n*m)
        # space : O(1)
        
        start, end = 0, len(needle)
        
        while end-1 < len(haystack):
            if haystack[start:end] == needle: return start
            else:
                start += 1
                end   += 1
            
        return -1
        
        '''
        # ==================================================
        #  Python built-in Function                        =
        # ==================================================
        try:
            return haystack.index( needle )
        except:
            return -1
        '''

🤖 Python3 (KMP)

🤖 Java