题目描述:
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
解析:
1.创建一个HashMap,把括号配对放进去。
2.创建一个stack(array),for循环遍历字符串,对于每一个字符,
如果map里有这个key,那说明它是个左括号,从map里取得相对应的右括号,把他push进stack里。
否则的话,它就是右括号,需要pop出stack里的第一个字符,然后看它是否等于当前的字符。
如果不相符,则返回false。
3.循环结束后,如果stack不为空,说明还剩一些左括号没有闭合,返回false,否则返回true。
Java:
public boolean isValid(String s) { HashMap<Character, Character> mappings = new HashMap<Character, Character>(); mappings.put('(', ')'); mappings.put('[', ']'); mappings.put('{', '}'); Stack<Character> stack = new Stack<Character>(); for(int i = 0; i < s.length(); i++) { char c = s.charAt(i); if(mappings.containsKey(c)) { stack.push(mappings.get(c)); } else { if(stack.size() == 0 || stack.pop() != c) { return false; } } } if(stack.size() != 0) { return false; } return true; }
JavaScript:
var isValid = function(s) { const mappings = new Map(); mappings.set("(", ")"); mappings.set("[", "]"); mappings.set("{", "}"); const stack = []; for(let i = 0; i < s.length; i++) { if(mappings.has(s[i])) { stack.push(mappings.get(s[i])); } else { if(stack.pop() !== s[i]) { return false; } } } if(stack.length !== 0) { return false; } return true; };