LeetCode​20题 有效的括号（Valid Parentheses）

题目描述：

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

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

做法

使用栈来进行辅助求解。 1、创建一个空栈； 2、使用循环对字符串进行遍历转3，遍历完毕退出循环转7； 3、如果当前字符为'('、'{'、'['则进栈，转2； 4、如果当前字符为')'、'}'、']'，转5； 5、如果栈为空，则返回false，匹配不成功，结束程序；栈不空，转6； 6、弹出栈顶元素，如果栈顶元素不是与当前遍历到的字符相匹配的括号，则返回false，匹配不成功，结束程序；否则转2； 7、如果栈为空，则匹配成功，返回true，程序结束；否则返回false，匹配不成功，程序结束。

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack_match = new Stack<Character>();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='(' || s.charAt(i)=='[' || s.charAt(i)=='{'){
                stack_match.push(s.charAt(i));
            }else if(s.charAt(i)==')' || s.charAt(i)==']' || s.charAt(i)=='}'){
                if(stack_match.isEmpty())
                    return false;
                char current = stack_match.pop();

                if(current == '(' && s.charAt(i)!=')')
                    return false;
                if(current == '[' && s.charAt(i)!=']')
                    return false;
                if(current == '{' && s.charAt(i)!='}')
                    return false;
            }
        }
        if(stack_match.isEmpty())
            return true;
        return false;
    }
}

案例说明

案例1：“（ ）” 1、创建空栈； 2、对字符串进行遍历； 3、第一个元素是”(” 进栈；当前栈中元素有”(”; 4、第二个元素是”)”，栈非空，弹出栈顶元素；栈顶元素为”(”,与”)”可以匹配； 5、字符串遍历完毕，栈空，返回true

案例2：“{ }[ ]” 1、创建空栈； 2、对字符串进行遍历； 3、第一个元素是”{” 进栈；当前栈中元素有”{”; 4、第二个元素是”}”，栈非空，弹出栈顶元素；栈顶元素为”{”,与”}”可以匹配； 5、第三个元素是”[”，进栈；当前栈中元素有”[”; 6、第二个元素是”]”，栈非空，弹出栈顶元素；栈顶元素为”[”,与”]”可以匹配； 7、字符串遍历完毕，栈空，返回true

案例3：”( ) ) ]” 1、创建空栈； 2、对字符串进行遍历； 3、第一个元素是”(” 进栈；当前栈中元素有”(”; 4、第二个元素是”)”，栈非空，弹出栈顶元素；栈顶元素为”(”,与”)可以匹配； 5、第三个元素是”)”，栈空，返回false，匹配不成功，程序结束。

案例4：”( ( ( { [ } ] ) )” 1、创建空栈； 2、对字符串进行遍历； 3、第一个元素是”(” 进栈；当前栈中元素有”(”; 4、第二个元素是”(” 进栈；当前栈中元素有”( (”;； 5、第三个元素是”(” 进栈；当前栈中元素有”( ( (”; 6、第四个元素是”{” 进栈；当前栈中元素有”( ( ( {”; 7、第五个元素是”[” 进栈；当前栈中元素有”( ( ( { [”; 8、第六个元素是”}”，栈非空，弹出栈顶元素；栈顶元素为”[”,与”}”不可以匹配，返回false，程序结束。

欢迎关注

扫下方二维码即可关注:

微信公众号:code随笔