Implement strStr() – Leetcode Python Solution

LeetCode has a Easy coding Problem in Its’ Algorithm Section “Implement strStr()”. Today We are going to solve this problem. LeetCode Link of the Problem is HERE

Question

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().

Examples

Input: haystack = "hello", needle = "ll"
Output: 2
Input: haystack = "aaaaa", needle = "bba"
Output: -1
Input: haystack = "", needle = ""
Output: 0

Constraints:

  • 0 <= haystack.length, needle.length <= 5 * 104
  • haystack and needle consist of only lower-case English characters.

Solution to Implement strStr()

The Skeleton code given by leetcode is

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        

Create two variables. Variable one with the value of the length of the haystack and variable 2nd with the value of the length of the needle.

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        len1=len(haystack)
        len2=len(needle)
        

Check for the first condition. In case the length of the needle is greater than the length of haystack return -1.

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        len1=len(haystack)
        len2=len(needle)
        if len2 > len1:
           return -1

Create a loop from 0 to length of haystack – length of needle. For example if haystack = “Hello” and needle = “ll”, create a loop from 0 to 5-2+1 = 2.

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        len1=len(haystack)
        len2=len(needle)
        if len2 > len1:
           return -1
        for i in range(len1 - len2 + 1):
           

Now Check for the characters in haystack. If haystack has characters == needle. return i else return -1.

Complete Solution:

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

READ MORE

Python-related posts Visit HERE

C++ related posts Visit HERE

Databases related posts Visit HERE

Data Structures related posts visit HERE

Algorithms related posts visit HERE

Data Science related posts visit HERE

Share the Knowledge