leetcode 20 : 有效的括号

leetcode 20 : 有效的括号

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

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。

  2. 左括号必须以正确的顺序闭合。

示例 1:

输入:s = "()"
输出:true

示例 2:

输入:s = "()[]{}"
输出:true

示例 3:

输入:s = "(]"
输出:false

示例 4:

输入:s = "([)]"
输出:false

示例 5:

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

提示:

  • 1 <= s.length <= 104

  • s 仅由括号 '()[]{}' 组成

Related Topics

字符串

思路1:栈

public boolean isValid(String s) {
    int length = s.length();
    char[] stack = new char[length];
    int last = -1;
    for(int i = 0 ; i < length;i++){
        char c = s.charAt(i);
        if(c == '(' || c == '{' || c=='['){
            stack[++last] = c;
        }else{ // ) ] } 进行匹配出栈
            if(last==-1 ){ //需要匹配时 没有元素 例:]][[
                return false;
            }
            //匹配成功 出栈
            if((c == ')' && stack[last] == '(') || (c == '}' && stack[last] == '{') || (c ==']' && stack[last] == '[')){
                last--;
            }else{//不成功
                return false;
            }
        }
    }
    return last==-1? true :false;
}

思路2:

对思路1改进:

public boolean isValid(String s) {
    int length = s.length();
    char[] stack = new char[length];
    int last = -1;
    for(int i = 0 ; i < length;i++){
        char c = s.charAt(i);
        // 左括号
        if(c == '(' || c == '{' || c=='['){
            stack[++last] = c;
            //匹配成功 出栈
        }else if(last != - 1 &&
                ((c == ')' && stack[last] == '(') ||
                        (c == '}' && stack[last] == '{') ||
                        (c ==']' && stack[last] == '[')
                )){
            last--;
        }else{//不成功
            return false;
        }
    }
    return last==-1;
}
上一篇:Android自定义TextView(一)实现圆角、反光效果


下一篇:LeetCode第71场双周赛