20. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路1：
用列表来模拟栈来做
程序代码1：
class Solution:
def isValid(self, s: str) -> bool:
s = s.replace("\"","")
length = len(s)
stack = []
for i in range(0, length):
if (s[i] == '{' or s[i] == '(' or s[i] == '['):
stack.append(s[i])
else:
if (len(stack) != 0):
tmp = stack.pop()
if (s[i] == '}' and tmp != "{"):
return False
if (s[i] == ')' and tmp != "("):
return False
if (s[i] == ']' and tmp != "["):
return False
else:
return False
if (len(stack) != 0):
return False
return True
s = Solution()
print(s.isValid(input()))
解题思路2：
用字典类模拟哈希表来做
程序代码2：
class Solution:
def isValid(self, s: str) -> bool:
s = s.replace("\"", "")
dic = {'(': ')', '[': ']', '{': '}'}
stack = []
for i in s:
if i in dic.keys():
stack.append(i)
elif i in dic.values():
if len(stack) == 0 or dic.get(stack[-1]) != i:
return False
else:
stack.pop()
if len(stack) == 0:
return True
else:
return False
s = Solution()
print(s.isValid(input()))
