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

Constraints:

• 0 <= haystack.length, needle.length <= 5 * 10^4

• haystack and needle consist of only lower-case English characters.

Input: haystack = "hello", needle = "ll"
Output: 2

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Input: haystack = "", needle = ""
Output: 0

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

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

        # ==================================================
        #  KMP Pattern Matching (Substring search)         =
        # ==================================================
        # n = length of haystack
        # m = length of needls
        # time  : O(n+m)
        # space : O(m)

        # (1) build LPS table (Longest proper Prefix also Suffix)
        # time  : O(n)
        # space : O(n)
        def LPS(string: str, length: int) -> list:
            '''
            Two pointers, jump and move, point to GOLDEN string
            '''
            jumpP, moveP = 0, 1
            table = [0] + [-1]*( length - 1 )

            while moveP < length:
                if string[jumpP] != string[moveP]:
                    if jumpP == 0:
                        table[moveP] = 0
                        moveP += 1
                    else:
                        jumpP = table[jumpP-1]

                else:
                    table[moveP] = jumpP + 1

                    jumpP += 1
                    moveP += 1

            return table

        # (2) use LPS table to do pattern matching
        # time  : O(m)
        # space : O(1)
        def KMP(str1: str, str2: str, LPSTable: list) -> int:
            '''
            Two pointers:
            - move pointer point to TARGET string (haystack)
            - jump pointer point to LPS table / GOLDEN string (needle)
            '''
            jumpP, moveP = 0, 0

            while moveP < len(str1):
                if str1[moveP] != str2[jumpP]:
                    if jumpP == 0:
                        moveP += 1
                    else:
                        jumpP = LPSTable[jumpP-1]

                else:
                    jumpP += 1
                    moveP += 1

                # Meet the end, return starting index
                if jumpP == len(str2): return moveP - len(str2)

            return -1

        LPSTable = LPS(needle, len(needle))
        return KMP(haystack, needle, LPSTable)

🤖 Java

class Solution {
    /**
     * @time  : O(n*m)
     * @space : O(1)
     */

    public int strStr(String haystack, String needle) {
        /* base case */
        if(needle.length() == 0) return 0;
        if(haystack.length() == 0 || needle.length() > haystack.length()) return -1;
        
        for(int i=0; i<(haystack.length()-needle.length()+1);i++) {
            if (haystack.substring(i,i+needle.length()).equals(needle)) return i;
        }
        return -1;
    }
}