leetcode第14題-最長公共前綴

編寫一個函數來查找字符串數組中的最長公共前綴。

如果不存在公共前綴，返回空字符串 ""。

示例 1:

輸入: ["flower","flow","flight"]
輸出: "fl"

示例 2:

輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴。

說明:
所有輸入只包含小寫字母 a-z 。

來源：力扣（LeetCode）
連結：
https://leetcode-cn.com/problems/longest-common-prefix

解答

def longestCommonPrefix(strs):
    """
    縱向掃描，將所有字符串縱向排序，從第1個字母依次往後對比，
    第1個不全相同的字母之前的則是最長公共前綴。
    :type strs: List[str]
    :rtype: str
    """
    if not strs:
        return ''
    result = ''
    strs.sort(key=len)  # 將列表按字符串長度從小到大排序
    for i in range(len(strs[0])):
        letter = strs[0][i]
        for n in range(len(strs)):
            if strs[n][i] != letter:
                return result
        result += letter
    return result


def longestCommonPrefix1(strs):
    """
    大神方法1：利用python的max()和min()，在Python裡字符串是可以比較的，
    按照ascII值排，舉例abb，aba，abac，最大為abb，最小為aba。
    所以只需要比較最大最小的公共前綴就是整個數組的公共前綴。
    """
    if not strs:
        return ''
    s1 = min(strs)
    s2 = max(strs)
    for i, x in enumerate(s1):
        if x != s2[i]:
            return s2[:i]
    return s1


def longestCommonPrefix2(strs):
    """
    大神方法2：利用python的zip函數，把str看成list然後把輸入看成二維數組，
    左對齊縱向壓縮，然後把每項利用集合去重，
    之後遍歷list中找到元素長度大於1之前的就是公共前綴。
    """
    if not strs:
        return ''
    result = ''
    s = map(set, zip(*strs))
    print s
    for i, x in enumerate(s):
        x = list(x)
        if len(x) > 1:
            break
        result += x[0]
    return result


if __name__ == "__main__":
    s1 = ["flower", "flow", "flight"]
    s2 = ["dog", "racecar", "car"]
    s3 = ["flower", "flow", "flowight"]
    s4 = ['abc', 'bbbb', 'abcdef']
    print longestCommonPrefix2(s1)