有效的括号( LeetCode 20 )

一、题目描述

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

有效字符串需满足:

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

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

二、题目解析

有效的括号满足以下几个条件:

  • 1、字符串的长度一定是偶数。
  • 2、括号的匹配遵循右括号和最近的一个左括号进行匹配,它们匹配成功才有可能是有效的括号

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效的括号( LeetCode 20 ):https://leetcode-cn.com/problems/valid-parentheses
class Solution {

    public boolean isValid(String s) {

        // 当字符串长度为奇数的时候,属于无效情况,直接返回 false
        if (s.length() % 2 == 1) {
             // 无效情况,返回 false
             return false;
        }

        //构建一个栈,用来存储括号
        Stack<Character> stack = new Stack<Character>();

        // 把字符串转换为数组的形式,方便获取字符串中的每个字符
        char charArray[] = s.toCharArray();

        // 遍历字符串数组中的所有元素
        for( int i = 0 ; i < charArray.length ; i++){

            // 获取此时的字符
            char c = charArray[i];   

            // 如果字符为左括号 ( ,那么就在栈中添加对左括号 (
            if(c == '('){

               // 添加对左括号 (
               stack.push('(');

             // 如果字符为左括号 [ ,那么就在栈中添加对左括号 [
            }else if(c == '['){

               // 添加对应的右括号 ]
               stack.push('[');

             // 如果字符为左括号 { ,那么就在栈中添加对左括号 {
            }else if( c == '{'){

               // 添加对应的右括号 }
               stack.push('{');

               // 否则的话,说明此时 c 是 )] } 这三种符号中的一种
            }else {

               // 如果栈已经为空,而现在遍历的字符 c 是 )] } 这三种符号中的一种
               // 找不到可以匹配的括号,返回 false
               // 比如这种情况  }{,直接从右括号开始,此时栈为空
               if(stack.isEmpty()) return false;

               // 如果栈不为空,获取栈顶元素
               char top = stack.peek();

               // 将栈顶元素和此时的元素 c 进行比较,如果相同,则将栈顶元素移除
               if( top == '(' && c == ')' || top == '[' && c == ']' || top == '{' && c == '}' ){
                   // 移除栈顶元素
                   stack.pop();
               }else{
                   // 如果不相同,说明不匹配,返回 false
                   return false;
               }

            }

        }

        // 遍历完整个字符数组,判断栈是否为空
        // 如果栈为空,说明字符数组中的所有括号都是闭合的
        // 如果栈为空,说明有未闭合的括号
        return stack.isEmpty();
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效的括号( LeetCode 20 ):https://leetcode-cn.com/problems/valid-parentheses
class Solution {
public:
    bool isValid(string s) {
        // 当字符串长度为奇数的时候,属于无效情况,直接返回 false
        if (s.size() % 2 == 1) {
             // 无效情况,返回 false
             return false;
        }

        //构建一个栈,用来存储括号
        stack<char> stk ;

        // 遍历字符串数组中的所有元素
        for( int i = 0 ; i < s.size() ; i++){

            // 获取此时的字符
            char c = s[i];   

            // 如果字符为左括号 ( ,那么就在栈中添加对左括号 (
            if(c == '('){

               // 添加对左括号 (
               stk.push('(');

             // 如果字符为左括号 [ ,那么就在栈中添加对左括号 [
            }else if(c == '['){

               // 添加对应的右括号 ]
               stk.push('[');

             // 如果字符为左括号 { ,那么就在栈中添加对左括号 {
            }else if( c == '{'){

               // 添加对应的右括号 }
               stk.push('{');

               // 否则的话,说明此时 c 是 )] } 这三种符号中的一种
            }else {

               // 如果栈已经为空,而现在遍历的字符 c 是 )] } 这三种符号中的一种
               // 找不到可以匹配的括号,返回 false
               // 比如这种情况  }{,直接从右括号开始,此时栈为空
               if(stk.empty()) return false;

               // 如果栈不为空,获取栈顶元素
               char top = stk.top();

               // 将栈顶元素和此时的元素 c 进行比较,如果相同,则将栈顶元素移除
               if( top == '(' && c == ')' || top == '[' && c == ']' || top == '{' && c == '}' ){
                   // 移除栈顶元素
                   stk.pop();
               }else{
                   // 如果不相同,说明不匹配,返回 false
                   return false;
               }

            }

        }

        // 遍历完整个字符数组,判断栈是否为空
        // 如果栈为空,说明字符数组中的所有括号都是闭合的
        // 如果栈为空,说明有未闭合的括号
        return stk.empty();

    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# // 有效的括号( LeetCode 20 ):https://leetcode-cn.com/problems/valid-parentheses
class Solution:
    def isValid(self, s: str) -> bool:
        # 当字符串长度为奇数的时候,属于无效情况,直接返回 False
        if len(s) % 2 == 1:
             # 无效情况,返回 False
             return False


        # 构建一个栈,用来存储括号
        stack = list()


        # 遍历字符串数组中的所有元素
        for c in s : 

            # 如果字符为左括号 ( ,那么就在栈中添加对左括号 (
            if c == '(' :

               # 添加对左括号 (
               stack.append('(')

             # 如果字符为左括号 [ ,那么就在栈中添加对左括号 [
            elif c == '[' :

               # 添加对应的右括号 ]
               stack.append('[')

             # 如果字符为左括号 { ,那么就在栈中添加对左括号 {
            elif c == '{' :

               # 添加对应的右括号 }
               stack.append('{')

               # 否则的话,说明此时 c 是 )] } 这三种符号中的一种
            else :

               # 如果栈已经为空,而现在遍历的字符 c 是 )] } 这三种符号中的一种
               # 找不到可以匹配的括号,返回 False
               # 比如这种情况  }{,直接从右括号开始,此时栈为空
               if not stack : 
                  return False

               # 如果栈不为空,获取栈顶元素
               top = stack[-1]

               # 将栈顶元素和此时的元素 c 进行比较,如果相同,则将栈顶元素移除
               if (top == '(' and c == ')' ) or (top == '[' and c == ']' ) or (top == '{' and c == '}')  :
                    # 移除栈顶元素
                    stack.pop()
               else :
                   # 如果不相同,说明不匹配,返回 False
                   return False


        # 遍历完整个字符数组,判断栈是否为空
        # 如果栈为空,说明字符数组中的所有括号都是闭合的
        # 如果栈为空,说明有未闭合的括号
        return not stack

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注

评论(1)

  • 陈芷维 永久会员 2021年10月17日 上午7:23

    class Solution {
    public boolean isValid(String s) {
    if (s.length() % 2 == 1) {
    return false;
    }
    int top = -1;
    int[] arrStack = new int[s.length()]; // 利用数组实现栈
    int index = 0; // 数组索引(栈的元素数)

    for (int i = 0; i < s.length(); i++) {
    char elem = s.charAt(i);
    if (elem == '(' || elem == '{' || elem == '[') {
    // 压栈
    arrStack[index] = elem;
    top = index;
    index++;
    } else {
    if (arrStack.length == 0 || top == -1) {
    return false;
    }
    // 括号匹配
    switch (elem) {
    case ')':
    if (arrStack[top] == '(') {
    top–;
    index–;
    } else {
    return false;
    }
    break;
    case '}':
    if (arrStack[top] == '{') {
    top–;
    index–;
    } else {
    return false;
    }
    break;
    case ']':
    if (arrStack[top] == '[') {
    top–;
    index–;
    } else {
    return false;
    }
    break;
    default:
    System.out.println("error!");
    }
    }
    }
    if (top == -1) {
    return true;
    } else {
    return false;
    }
    }
    }