Implement strStr()

Implement strStr().

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

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

思路很简单，明显two pointers循环，但是很难一次写对，主要是特殊条件的判断，以及超时的优化需要注意：循环的结束应该是lengthh - lengthn + 1，减少不必要运算, 同时注意，比较所有子字符串的字母所以是haystack[i+j] 与needle[j]。

这道题让我们在一个字符串中找另一个字符串第一次出现的位置，那首先要做一些判断，如果子字符串为空，则返回0，如果子字符串长度大于母字符串长度，则返回 -1。然后开始遍历母字符串，这里并不需要遍历整个母字符串，而是遍历到剩下的长度和子字符串相等的位置即可，这样可以提高运算效率。然后对于每一个字符，都遍历一遍子字符串，一个一个字符的对应比较，如果对应位置有不等的，则跳出循环，如果一直都没有跳出循环，则说明子字符串出现了，则返回起始位置即可，代码如下：

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

        lengthh = len(haystack)
        lengthn = len(needle)
        if lengthn == 0:
            return 0
        if lengthh < lengthn:
            return -1
        for i in xrange(lengthh - lengthn + 1):
            j = 0
            while j < lengthn:
                if haystack[i+j] != needle[j]:
                    break
                else:
                    j += 1
            if j == lengthn:
                return i
        return -1

简化

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