Longest Common Prefix

Question

Given k strings, find the longest common prefix (LCP).

Example

For strings "ABCD", "ABEF" and "ACEF", the LCP is "A"

For strings "ABCDEFG", "ABCEFG" and "ABCEFA", the LCP is "ABC"

Thoughts

lcp先等于第一个，然后一个一个比较过去

注意点

• 每次更新lcp
• lcp和当前string的长度

Solution

class Solution:
    # @param strs: A list of strings
    # @return: The longest common prefix
    def longestCommonPrefix(self, strs):
        # write your code here
        if not strs:
            return ""
        lcp = strs[0]
        for i in range(1, len(strs)):
            lcpLen = len(lcp)
            curLen = len(strs[i])
            comLen = min(lcpLen, curLen)
            index = 0
            while index < comLen:
                if lcp[index] == strs[i][index]:
                    index += 1
                else:
                    break
            lcp = lcp[:index]
        return lcp