LeetCode – Valid Parentheses

题目:

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

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. 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

解题:

      创建栈, 遇到左括号'(''[''{' 将其入栈, 遇到右括号')'']''}' ,   判断栈顶是不是对应的左括号, 对应出栈, 否则返回失败, 循环完毕后,判断栈是否为空,空则表示完全匹配。

 

实现:

class Solution {
public:
    bool isValid(string s) {
        stack<char>  ss;
        for (int i=0; i<s.size(); i++){
            if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
                ss.push(s[i]);
            }
            else{
                if (ss.empty()) return false;
                if (s[i] == ')' && ss.top() != '(') return false;
                if (s[i] == ']' && ss.top() != '[') return false;
                if (s[i] == '}' && ss.top() != '{') return false;
                ss.pop();
                    
            }
        }
        return ss.empty();
    }
};

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注