Leetcode 14: Longest Common Prefix

 

Code

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ""
        
        prefix = ""
        for k in xrange(len(strs[0])):
            for i in xrange(1, len(strs)):
                if k < len(strs[i]) and strs[i][k] == strs[0][k]:
                    continue
                return prefix
            prefix += strs[0][k]
        
        return prefix

 

Idea

Suppose there are N strings and average K length for each string. Then this algorithm takes O(NK) time, which I believe is the fastest solution so far. Note that we start prefix from an empty string. In this way, we only need to test whether to add one character to prefix each time. 

 

Reference: https://discuss.leetcode.com/topic/20991/accepted-c-6-lines-4ms/6