20 Valid Parentheses

Leetcode

Given a string s 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.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

---

可以使用栈来模拟括号

public boolean isValid(String s) {
    Deque<Character> stack = new LinkedList<>();
    for(int i=0;i<s.length();++i){
        char c=s.charAt(i);
        if(c=='(' || c=='{' || c=='['){
            stack.push(c);
        } else {
            if(stack.isEmpty()) return false;
            char p=stack.peek();
            if((c==')' && p=='(') ||
                (c=='}' && p=='{') ||
                (c==']' && p=='[')){
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

bool isValid(string s) {
    vector<char> stack;
    int len=s.length();
    for(int i=0;i<s.length();++i){
        char c=s[i];
        if(c=='(' || c=='{' || c=='['){
            stack.push_back(c);
        } else {
            if(stack.empty()) return false;
            char p = stack[stack.size()-1];
            if((c==')' && p=='(') ||
                (c=='}' && p=='{') ||
                (c==']' && p=='[')){
                stack.pop_back();
            } else {
                return false;
            }
        }
    }
    return stack.empty();
}