每日Leetcode—算法（2）

14.最长公共前缀

输入: ["flower","flow","flight"]，输出: "fl"
输入: ["dog","racecar","car"]，输出: ""
解释: 输入不存在公共前缀。

算法一：

def longestCommonPrefix(self, strs: List[str]) -> str:
    if not strs: return ''
    if len(strs) == 1: return strs[0]

    minl = min([len(x) for i in strs])   #找到长度最小的字符串
    end = 0
    while end<minl:
        for i in range(1,len(strs)):   #循环比对字符
            if strs[i][end] != strs[i-1][end]:
                return strs[i][:end]    #直到比对不相等
        end+=1
    return strs[0][:end]      #遇到空字符串，返回空

算法二：

if len(strs)==0: return ''
res = ''
for each in zip(*strs):      #利用zip函数将对象中对应的元素打包成一个个元组
    if len(set(each)) == 1: #set函数可创造一个无序不重复元素集，元素集长度为1时，元素相等
        res += each[0]    #将相等元素添加到res中
    else:
        return res     #将之前的相等元素返回
return res

分析：该算法使用zip函数和set函数将原本问题进行了简化。

算法三：

if len(strs)==0: return ''
s1 = min(strs)
s2 = max(strs)
for i,x in enumerate(s1):     #使用枚举的方法
    if x != s2[i]:
        return s2[:i]        #碰到两字符不相等时，则返回
return s1

分析：该方法利用了max()和min()函数，在python语言中字符串是可以比较的，按照ascII值排，举例abb， aba，abac，最大为abb，最小为aba。所以只需要比较最大最小的公共前缀就是整个数组的公共前缀。

20.有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
示例：

输入: "()"，输出: true
输入: "()[]{}"，输出: true
输入: "([)]"，输出: false
输入: "{[]}"，输出: true

算法一：

def isValid(self, s: str) -> bool:
    if len(s)%2 == 1:  return False    #首先排除奇数字符串
    stack = []
    mapping = {'(':')','{':'}','[':']'}
    for x in s:               #对每个字符进行条件查看
        if x in mapping:
            stack.append(x)     #如果字典中包含key，则将value存入stack
        else:
            if not stack or mapping[stack.pop()] != x:   #对比成功后，pop尾端字符，目的是保持stack为初始状态
                return False    #如果stack为空，或者x不等于存入stack的key的对应value，返回False
    return stack==[]     #s为空，返回True

算法二：

if len(s)%2 == 1: return False
stack = [None]
mapping = {')':'(','}':'{',']':'['}   #与算法一相反的key-value
for x in s:        #if-else与算法一的相反
    if x in mapping and mapping[x] == stack[-1]:     #如果x在字典中，且与stack的最后一个字符相同，则pop掉stack的末尾字符，目的是使stack保持为初始状态
        stack.pop()
    else:
        stack.append(x)
return len(stack) == 1    #与算法一不同，stack初始不为空，因为在循环时需要使用stack[-1]

分析：算法一与算法二属于相反的查找顺序，只是一些细节需要注意。