Skip to content

20. Valid Parentheses

20. Valid Parentheses

难度: Easy

刷题内容

原题连接 * https://leetcode-cn.com/problems/valid-parentheses/

内容描述

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

2. Input: "()[]{}" -> Output: true

3. Input: "(]" -> Output: false

4. Input: "([)]" -> Output: false

5. Input: "{[]}" -> Output: true

解题方案

思路:

利用栈先进后出的先天优势,解决匹配问题。
bool isValid(string s) {
        stack<char> stacks;
        for(int i=0;i<s.length();i++){
            if(s[i]=='('||s[i]=='{'||s[i]=='[')
                stacks.push(s[i]);
            else if(stacks.empty()){
                return false;
            }else{
                char ch = stacks.top();
                stacks.pop();
                if(s[i]==')'&&ch=='('||s[i]==']'&&ch=='['||s[i]=='}'&&ch=='{')
                    continue;
                else
                    return false;
            }
        }
        if(stacks.empty())
            return true;
        else
            return false;
    }



回到顶部