Leetcode: Longest Common Prefix

Longest Common Prefix | LeetCode OJ

The trick here is to pick the lexicographically first and last string and find the common prefix for them.

Remarks:

1. For n strings, O(n)*O(m) time to find min another O(n)*O(m) to find max assuming string comparison takes O(m) time where m is the length of longest string. After that we take an additional O(m) time to compare the final 2 strings
2. O(1) space as no additional copies of strings are made

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ''
        s1 = min(strs)
        s2 = max(strs)
        for i, c in enumerate(s1):
            if c != s2[i]:
                return s1[:i]
        return s1