Brute-force Python Solution with Clear Explanation

  • 0

    This method is based on Brute-Force Algorithm. The basic idea is:
    Given a target string S and a pattern string T:

    1. Compare the 1st bit of S and 1st bit of T;
    2. 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]:
                    j += 1
                i += 1

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.