This method is based on Brute-Force Algorithm. The basic idea is:
Given a target string S and a pattern string T:
- Compare the 1st bit of S and 1st bit of T;
- If equal, compare the 2nd bit of S and 2nd bit of T; if not equal, compare the 2nd bit of S and 1st bit of T.
Algorithm can run all the way to the end where a specific requirement is reached.
My posted code can be shorten, but from runtime speed's aspect, it is usually a good idea to use variables to store values that will appear many times in the program.
Open to any suggestion, thanks.
class Solution(object): def strStr(self, haystack, needle): length1 = len(needle) length2 = len(haystack) i = 0 # The start index of haystack j = 0 # The index of needle while True: j = 0 while True: if j == length1: return i if i+j == length2: return -1 if needle[j] != haystack[i+j]: break j += 1 i += 1