28. Implement strStr()

Implement strStr().

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

1 class Solution(object):
2     def strStr(self, haystack, needle):
3         """
4         :type haystack: str
5         :type needle: str
6         :rtype: int
7         """
8         return haystack.find(needle)

2 brute force

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        result = -1
        l_needle = len(needle)
        l_haystack = len(haystack)
        if l_needle == 0 and l_haystack == 0:
            return 0
        if l_haystack == 0 and l_needle!=0:
            return result    
        if l_needle == 0 :
            return 0
        for index in range(l_haystack):
            if l_haystack - index  >= l_needle and needle == haystack[index:index+l_needle]:
                result = index
                break
        return result

3 hash 有待改进

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        result = -1
        l_needle = len(needle)
        l_haystack = len(haystack)
        if l_needle == 0 and l_haystack == 0:
            return 0
        if l_haystack == 0 and l_needle!=0:
            return result    
        if l_needle == 0 :
            return 0
        if l_needle>l_haystack:
            return result
        hash_needle=hash(needle)
        list_haystack=[]
        for index in range(l_haystack):
            if index<=(l_haystack-l_needle):
                list_haystack.append(hash(haystack[index:index+l_needle]))
        result=list_haystack.index(hash_needle) if hash_needle in  list_haystack else -1 
        return result