strStr

For a given source string and a target string, you should output the first index(from 0) of target string in source string.

If target does not exist in source, just return -1.

Example

If source = “source” and target = “target”, return -1.

If source = “abcdabcdefg” and target = “bcd”, return 1.

Challenge

O(n²) is acceptable. Can you implement an O(n) algorithm? (hint: KMP)

Solution

Be careful about the corner cases. (e.g. NULL, emptry string)

(strStr.py) download

class Solution:
    def strStr(self, source, target):
        # write your code here
        j = 0

        # None string is NULL
        if source == None or target == None:
            return -1

        # target is empty
        if target == "":
            return 0

        for i in range(len(source)) :
            source_index = i
            while target[j] == source[source_index] and j < len(target) :
                source_index += 1
                j += 1
                if j == len(target) :
                    return i
            j = 0
        return -1