卖萌的弱渣

I am stupid, I am hungry.

Longest Common Prefix

Longest Common Prefix

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”

Solution

  • Find the shortest string
  • Compare each character of the shortest string with other strings. Return the result if any comparison returns false
(Longest-Common-Prefix.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    # @param strs: A list of strings
    # @return: The longest common prefix
    def longestCommonPrefix(self, strs):
        # write your code here
        result = ""
        if strs == None :
            return result
        if len(strs) == 0:
            return result

        min_len = sys.maxint
        min_str = 0
        for i in range(len(strs)):
            if min_len > len(strs[i]):
                min_len = len(strs[i])
                min_str = i
        if min_len == 0:
            return result
        for i in range(len(strs[min_str])):
            for index in range(len(strs)) :
                if strs[min_str][i] != strs[index][i]:
                    return result
            result += strs[min_str][i]

        return result