Valid Parenteses

文章目录

1. 1. Valid Parenthese
   1. 1.1. 题目
   2. 1.2. 思路
   3. 1.3. 解题　

Valid Parenthese

题目

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.

思路

建立一个栈，遇到左边的括号，将其入栈，遇到右边的括号，若栈为空，则返回False，若不空，将栈顶元素出栈，并与右边的括号进行配对，若配对不成功，则返回False。重复上述步骤。若最终栈为空，则为True。否则返回False。

解题　

c++版

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

python版

class Solution:
    # @return a boolean
    def isValid(self, s):
        ss=[]
        for char in s:
            if char in ['(','{','[']:
                ss.append(char)
            if char==')':
                if len(ss)==0 or ss[-1]!='(':
                    return False
                else:
                    ss.pop()
            if char=='}':
                if len(ss)==0 or ss[-1]!='{':
                    return False
                else:
                    ss.pop()
            if char==']':
                if len(ss)==0 or ss[-1]!='[':
                    return False
                else:
                    ss.pop()
        if len(ss)==0:
            return True
        return False