給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。
有效字符串需滿足：
1.左括號(hào)必須用相同類(lèi)型的右括號(hào)閉合。
2.左括號(hào)必須以正確的順序閉合。
注意空字符串可被認(rèn)為是有效字符串。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
解法 1：
利用堆棧，遍歷字符串的每個(gè)輸入字符，如果是左括號(hào)，將其壓入堆棧，如果是右括號(hào)，則從棧頂彈出左括號(hào)，如果棧頂左括號(hào)和輸入右括號(hào)不匹配或堆棧為空，則說(shuō)明不是有效字符串。
def is_valid(s):
stack = []
c_map = {')': '(', '}': '{', ']': '['}
for c in s:
if c not in c_map:
stack.append(c)
elif not stack or c_map[c] != stack.pop():
return False
return not stack
執(zhí)行用時(shí) :16 ms
內(nèi)存消耗 :11.9 MB
時(shí)間復(fù)雜度：壓棧和出棧及 map 查找的時(shí)間復(fù)雜度都為 O(1)，每個(gè)左括號(hào)都需壓棧和出棧， 每個(gè)右字符都需要 map 查找，所以時(shí)間復(fù)雜度為 O(n)。
空間復(fù)雜度：最糟糕的情況是將所有符號(hào)堆到棧上，所以空間復(fù)雜度為 O(n)。
解法 2：
遍歷字符串將所有對(duì)稱括號(hào)替換為空字符，判斷最后結(jié)果是否為空，通過(guò)比較替換前后的字符串長(zhǎng)度來(lái)判斷是否需要繼續(xù)替換。
def is_valid(s):
lenth = 0
while len(s) != lenth:
lenth = len(s)
s = s.replace('()', '').replace('{}', '').replace('[]', '')
return len(s) == 0
執(zhí)行用時(shí) :52 ms
內(nèi)存消耗 :12 MB
時(shí)間復(fù)雜度為：
空間復(fù)雜度為：O(1)
