14. Longest Common Prefix

2019-03-28

14. 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:

1
2
Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

1
2
3
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.

Code：

1
2
3
4
5
6
7
8
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        minL = min(map(len, strs)) if strs else 0
        for i in range(minL):
            for j in range(1, len(strs)):
                if strs[j][i] != strs[0][i]:
                    return strs[0][:i]
        return strs[0][0:minL] if minL else ""
1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def longestCommonPrefix(self, strs):
        prefix = '';
        # * is the unpacking operator, essential here
        for z in zip(*strs):# 反向拆
            bag = set(z);# 创建集合，集合不能有重复的
            if len(bag) == 1:
                prefix += bag.pop(); # 删除并返回
                print(prefix)
            else:
                break;
        return prefix;
-->