LeetCode: Implement strStr()

\(\)

Description

Implement strStr().

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

Example 1:

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

Example 2:

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

C++ Solution

Time complexity: \(O(MN)\) where M and N are the lengths of two string.

class Solution {
public:
  int strStr(string haystack, string needle) {
    int len1 = haystack.size();
    int len2 = needle.size();
    for(int i = 0; i <= len1 - len2; i++) {
      int k = 0;
      while(k < len2 && haystack[i+k] == needle[k])
        k++;
      if(k == len2) return i;
    }
    return -1;
  }
};

Python Solution

Use str[i:length] to get the sub-string of str.

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if needle == '':
            return 0
        length = len(needle)
        for i in range(len(haystack) - length+1):
            if haystack[i:i+length] == needle:
                return i
        return -1

Preparing for an interview? Check out this!

Last Updated on

Leave a Reply

Your email address will not be published. Required fields are marked *