Python O(n) solution with very clear explanation

  • 0
    class Solution(object):
        def longestCommonPrefix(self, strs):
            :type strs: List[str]
            :rtype: str
            if not strs:
                return ""
            res = strs[0]
            for s in strs:
                # if res has shrinked to empty or encounter an empty string, return result immediately
                if s == "" or res == "":
                    return ""
                # if res == s, skip to next string
                if res == s:
                # compare res and other string from index 0
                startIndex = 0
                # find the break point where the common prefix may shrink
                while startIndex < len(s) and startIndex < len(res) and s[startIndex] == res[startIndex]:
                    startIndex += 1
                # update the res
                res = res[0:startIndex]
            return res

    We start to treat the first string as the "common prefix". Then we compare this "common prefix" with other strings, after each comparison, there are only two results:

    1. "common prefix" stays the same
    2. "common prefix" becomes shorter

    No matter which result happens, it has no impact on the previous strings, so after we traversed all the strings in the array, we can get the final "common prefix".

Log in to reply

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