题解 | #括号序列#
括号序列
http://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2
算法思想一：栈+哈希表
解题思路：
算法流程
1、构建哈希表 k，其中key为 右括号，value为左括号
2、遍历字符串
1、判断字符是否在 k.values() 中；
若在其中则字符入栈；
否则判断栈是否为空 或者 该字符的 values 是否与 栈顶元素相同；若不同则直接返回 false，若相同则栈顶元素出栈
3、判断栈内元素是否为空，为空则返回 true，反之返回 false
图解：
代码展示：
Python版本
class Solution:
def isValid(self , s ):
# write code here
# 哈希表
k = {'}':'{', ')':'(', ']':'['}
stack = []
# 遍历字符串
for a in s:
if a in k.values():
stack.append(a)
elif not stack&nbs***bsp;k[a] != stack.pop():
return False
# 如果栈内没有字符则表示 true，反之则 false
return len(stack) == 0 复杂度分析
时间复杂度O(N)：N表示字符串的长度，遍历字符串
空间复杂度O(N)：最差情况下栈内存储n个字符串，哈希表存储空间
算法思想二：栈
解题思路：
建立一个栈，存储遍历的字符串再进行对比 1、遍历字符串遇到 ‘(’ '[' '{' 左括号，就把相应的右括号（‘)’ ']' '}'）入栈
2、如果遍历遇到右括号 ‘)’ ']' '}' ，则判断是否和栈顶元素相同
1、不同则直接返回false
2、相同则将栈顶元素出栈
3、遍历结束判断栈是否为空
图解：
代码展示：
JAVA版本
import java.util.*;
public class Solution {
/**
*
* @param s string字符串
* @return bool布尔型
*/
public boolean isValid (String s) {
// write code here
Stack<Character>stack = new Stack<Character>();
for(char c: s.toCharArray()){
// 碰到左括号，就把相应的右括号入栈
if(c=='(')stack.push(')');
else if(c=='[')stack.push(']');
else if(c=='{')stack.push('}');
// 如果是右括号判断是否和栈顶元素匹配
else if(stack.isEmpty()||c!=stack.pop())return false;
}
// 最后判断栈中元素是否匹配
return stack.isEmpty();
}
} 复杂度分析
时间复杂度O(N)：N表示字符串的长度，遍历字符串
空间复杂度O(N)：最差情况下栈内存储n个字符串
民生银行工作强度 61人发布
