menu

[LeetCode] 014. Longest Common Prefix

Problem （Easy）

014. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

Example 1:

  • Input: [“flower”,”flow”,”flight”]
  • Output: “fl”

Example 2:

  • Input: [“dog”,”racecar”,”car”]
  • Output: “”
  • Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Approach 1: Vertical Scanning

Idea

Scan all the strings in the list character by charcter columnwise. if all characters in the column are the same, add it to LCP, else, return current LCP directly.

Solution

class Solution1:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not len(strs):
            return ''
        ret = ''
        for i in range(min([len(s) for s in strs])):
            for s in strs[1:]:
                if strs[0][i] != s[i]:
                    return ret
            ret += strs[0][i]
        return ret

Complexity

  • Time: $O(S)$, where $S$ is the sum of the all characters.
  • Space: $O(1)$. We only need constant extra space.

Approach 2: Horizontal Scanning

Idea

Find the LCP of each pair of strings in loops.

Solution

class Solution2:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not len(strs):
            return ''
        ret = strs[0]
        for s in strs[1:]:
            ret = ret[:min(len(ret), len(s))]
            for i in range(len(ret)):
                if ret[i] != s[i]:
                    ret = ret[:i]
                    break
        return ret

Complexity

  • Time: $O(S)$
  • Space: $O(1)$

Approach 3: Divide and Conquer

Idea

Solution

class Solution3:
    def longestCommonPrefix(self, strs):
        """ 
        :type strs: List[str]
        :rtype: str
        """
        if not len(strs):
            return ''
        return self.recurse(strs)

    def recurse(self, strs):
        if len(strs) == 1:
            return strs[0]
        mid = len(strs) // 2
        lcpLeft = self.recurse(strs[:mid])
        lcpRight = self.recurse(strs[mid:])

        return self.commonPrefix(lcpLeft, lcpRight)

    def commonPrefix(self, str1, str2):
        ret = str1[:min(len(str1), len(str2))]
        for i in range(len(ret)):
            if ret[i] != str2[i]:
                ret = ret[:i]
                break
        return ret

Complexity

  • Time: $O(S)$, where $S=m*n$. In the best case, it’s $O(minLen\cdot n)$, where $minLen$ is the shortest string of the array.
  • Space: $O(m\cdot \log(n))$.

Idea

The idea is to apply binary search method to find the string with maximum value L,

Solution

class Solution4:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not len(strs):
            return ''
        minLen = min([len(s) for  s in strs])
        low, high = 0, minLen
        while low <= high:
            mid = (low + high) // 2
            if self.isCommonPrefix(strs, mid):
                low = mid + 1
            else:
                high = mid -1
        return strs[0][:(low+high) // 2]

    def isCommonPrefix(self, strs, l):
        str1 = strs[0][:l]
        for s in strs[1:]:
            if not s.startswith(str1):
                return False
        return True

Complexity

  • Time: $O(S\cdot\log(n))$
  • Space: $O(1)$



KF

Comments