LeetCode 括号匹配 20. Valid Parentheses

谁借莪１个温暖的怀抱￠ 2022-03-09 16:46 139阅读 0赞

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
    Example 2:
    
    Input: "()[]{}"
    Output: true
    Example 3:
    
    Input: "(]"
    Output: false
    Example 4:
    
    Input: "([)]"
    Output: false
    Example 5:
    
    Input: "{[]}"
    Output: true

给我们一个括号的字符串，看它的括号是否匹配。  
第一种思路：遍历字符串，使用栈存储遍历的字符：

*  当遍历到的字符是‘)’，‘\}’，‘\]’时
    
     *  如果栈不为空判断栈顶字符是否是‘(’，‘\{’，‘\[’，如果是，栈顶字符出栈，如果不是，返回false。
     *  如果栈为空，直接返回false。//①
 *  当遍历到的字符是‘(’，‘\{’，‘\[’，则入栈。
 *  最后判定栈是否为空，为空返回true，否则返回false。

class Solution { 
        public boolean isValid(String s) { 
            Stack<Character> stack = new Stack<Character>();
            for (char c : s.toCharArray()) { 
            	if(stack.isEmpty() && (c == ')' || c == '}' || c == ']'))return false;//①这个判断不加也行
            	
                if (c == ')' && !stack.isEmpty()){ //栈不空出栈判断
                    if(stack.pop() != '(') return false;
                }else if (c == '}' && !stack.isEmpty()){ 
                    if(stack.pop() != '{') return false;
                }else if (c == ']' && !stack.isEmpty()){ 
                    if(stack.pop() != '[') return false;
                }else{ 
                    stack.push(c);//栈为空或者字符为‘(’，‘{’，‘[’时入栈
                }
            }
            return stack.isEmpty();
        }
    }

‘(’，‘\{’，‘\[’ ‘)’，‘\}’，‘\]’  
第二种思路：遍历字符串，使用栈存储遍历的字符：

*  当遍历到的字符是‘(’，‘\{’，‘\[’时我们将 ‘)’，‘\}’，‘\]’入栈。
 *  当遍历到的字符是‘)’，‘\}’，‘\]’时
    
     *  栈为空返回false。
     *  栈不为空判断栈顶元素是否和遍历到的字符相等，相等出栈，不相等返回false。
 *  最后判定栈是否为空，为空返回true，否则返回false。

class Solution { 
        public boolean isValid(String s) { 
            Stack<Character> stack = new Stack<Character>();
            for (char c : s.toCharArray()) { 
                if (c == '(')
                    stack.push(')');
                else if (c == '{')
                    stack.push('}');
                else if (c == '[')
                    stack.push(']');
                else if (stack.isEmpty() || stack.pop() != c)
                    return false;
            }
            return stack.isEmpty();
        }
    }