leetcode [#20]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

---

解决方案

public class Solution {
    public boolean isValid(String s) {
        char[] sArr = s.toCharArray();
        Stack<String> stack = new Stack<>();
        boolean result = true;
        for(int i = 0; i < sArr.length; i++){
            if(sArr[i] == '(' || sArr[i] == '[' || sArr[i] == '{'){
                stack.push(String.valueOf(sArr[i]));
            } else {
                if(stack.empty()){
                    result = false;
                    break;
                } else {
                    if(sArr[i] == ')'){
                        if(!"(".equals(stack.pop())){
                            result = false;
                            break;
                        }
                    }
                    if(sArr[i] == ']'){
                        if(!"[".equals(stack.pop())){
                            result = false;
                            break;
                        }
                    }
                    if(sArr[i] == '}'){
                        if(!"{".equals(stack.pop())){
                            result = false;
                            break;
                        }
                    }
                }
            }
        }
        if(!stack.empty()){
            result = false;
        }
        return result;
    }
}

---

注意事项

1. 要求三种括号能够正确匹配。
2. 使用数据结构栈来实现：每当遇到一组括号的“左部分”，压入堆栈；每当遇到“右部分”，堆栈弹出一个元素，与当前的“右部分”相比，看能否匹配。