一, 题目
- Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
- An input string is valid if:
??Open brackets must be closed by the same type of brackets.
??Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
- Example 1:
- ??Input: "()"
- ??Output: true
- Example 2:
- ??Input: "()[]{}"
- ??Output: true
- Example 3:
- ??Input: "(]"
- ??Output: false
- Example 4:
- ??Input: "([)]"
- ??Output: false
- Example 5:
- ??Input: "{[]}"
- ??Output: true
二, 解题思路
1, 利用 List 集合实现一个栈;
2, 将字符串 s 转换成字符数组, 并循环遍历;
3, 如果字符为:"{,(,[" 中的一个, 则存入集合中;
4, 如果字符为:"},),]" 中的一个, 则取出集合中最后一个元素进行比较;
5, 如能匹配上, 则删除集合中最后一个元素, 否则返回 false;
6, 最后判断集合大小是否为 0, 如是则返回 true.
三, 代码实现
- public boolean isValid(String s) {
- if ("".equals(s)) {
- return true;
- } else {
- Map<Character, Character> parentheseMap = new HashMap<Character, Character>();
- parentheseMap.put(')', '(');
- parentheseMap.put(']', '[');
- parentheseMap.put('}', '{');
- char[] sArr = s.toCharArray();
- List<Character> stackList = new ArrayList<Character>();
- for (int i = 0; i < sArr.length; i++) {
- if (sArr[i] == '(' || sArr[i] == '[' || sArr[i] == '{') {
- stackList.add(sArr[i]);
- } else {
- if (stackList.size() == 0) {
- return false;
- } else {
- char temp = stackList.get(stackList.size() - 1);
- if (temp == parentheseMap.get(sArr[i])) {
- stackList.remove(stackList.size() - 1);
- } else {
- return false;
- }
- }
- }
- }
- return stackList.size() == 0 ? true : false;
- }
- }
来源: http://www.bubuko.com/infodetail-3073200.html