LeetCode——有效的括号

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true

一、CPP 栈

解题思路：这个问题经典的解法就是使用栈，当遇到左括号就入栈，遇到右括号就与栈顶的元素进行匹配，由于栈是后入先出，而只要遇到右括号，其左括号刚入栈，就一定在栈顶。匹配成功之后弹出栈顶元素继续上述操作，如果到最后栈为空，则说明匹配成功。出现不成功的情况有：
1.当开始就遇到右括号==>status1解决
2.中途左右括号不匹配==>status2解决
3.匹配完成之后栈不为空，说明有左括号未匹配==>status3解决

时间复杂度：O(n)。

class Solution {
public:
    bool isValid(string s) {
        stack<int> mystack;
        for(int i=0;i<s.size();i++)
        {   

            if(s[i]=='{' || s[i]=='[' || s[i]=='(')
            {
                mystack.push(s[i]);
            }
            else
            {
                //status1
                if(mystack.empty())
                {
                    return false;
                }

                char c = mystack.top();
                mystack.pop();
                
                //status2
                switch(s[i])
                {
                    case '}': 
                        if(c == '{'){break;}
                        else{ return false;}
                    case ']': 
                        if(c == '['){break;}
                        else{ return false;}
                    case ')': 
                        if(c == '('){break;}  
                        else{ return false;}

                    default: return false;
                    
                }
            }
        }
        
        //status3
        if(mystack.empty())
        {
            return true;
        }
        else
        {
            return false;
            
        }      
    }
};

二、Java stack

class Solution {
    public boolean isValid(String s) {
        // 空字符串
        if (s.length() == 0)
            return true;
        // 排除奇数长度(位运算)
        if ((s.length() & 1) == 1)
            return false;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
           //charAt()用于返回字符串指定索引处的字符。 (0 ，length() - 1）。
            switch (s.charAt(i)) {
                case '(':
                case '[':
                case '{':
                    stack.push(s.charAt(i));
                    continue;
                case ')':
                    if (stack.isEmpty() || stack.pop() != '(')
                        return false;
                    continue;
                case ']':
                    if (stack.isEmpty() || stack.pop() != '[')
                        return false;
                    continue;
                case '}':
                    if (stack.isEmpty() || stack.pop() != '{')
                        return false;
                    continue;
            }
        }
        return stack.isEmpty();
    }
}

三、Python

栈只是一种先进后出的数据结构，python中虽然没有栈的现成定义，但是完全可以用数组(list)模拟栈。并且list中pop、append方法也和cpp中作用相同，甚至比其更强大。

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        dict={")":"(","}":"{","]":"["}
        stack=[]
        for i in range(len(s)):
            if s[i] in dict :
                if stack:
                    if stack[-1]==dict[s[i]] :
                        stack.pop()
                    else:
                        return False
                else:
                    return False
            else:
                stack.append(s[i])
        return not stack

四、各语言及算法时间复杂度

各语言及算法时间复杂度