LeetCode-Valid Parentheses

https://leetcode.com/problems/valid-parentheses/description/

括号匹配的问题,记录左括号,寻找右括号是否匹配,用栈实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
pairSym={
'(':')',
'[':']',
'{':'}'
}
leftStack=[]
for sym in s:
if sym in pairSym.keys():
leftStack.append(sym)
else:
if len(leftStack) == 0 or sym != pairSym[leftStack.pop()]:
return False
if len(leftStack) == 0:
return True
else:
return False

用时 62ms,时间比较慢,需要寻找更高效的办法(可能少用一些哈希表效果会比较好),明天再试试

使用 Java,思路和 Python 相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public boolean isValid(String s) {
HashMap<Character,Character> parenthMap=new HashMap<Character,Character>(){{
put('{','}');
put('[',']');
put('(',')');
}};
Stack<Character> validStack=new Stack<Character>();
for(int i=0;i<s.length();i++){
Character parenth=s.charAt(i);
if(parenth=='('||parenth=='['||parenth=='{'){
validStack.push(parenth);
}else{
if(validStack.empty()){
return false;
}
Character validParenth=validStack.pop();
if(parenthMap.get(validParenth)!=parenth){
return false;
}
}
}
return validStack.empty();
}
}

运行时间打败 54.7%的人