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%的人