个人中心
gpt4 book ai didi

20. Valid Parentheses 有效的括号

转载 作者：大佬之路 更新时间：2024-01-31 14:22:21 25 4
gpt4 key购买 nike

本文关键词：有效，括号，括号匹配，栈，题解，leetcode, 力扣，Python, C++, Java

题目地址：https://leetcode.com/problems/valid-parentheses/#/descriptionopen in new window

题目描述

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Thebrackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

题目大意

有三种括号组成的字符串，看最后的结果是否能组成正常的括号。

解题方法

Java解法

第一感觉就是栈，但是怎么用呢。这个方法就是如果左边的括号出现，那么把右边的括号放到栈里，这样，如果不是左边的括号出现时，弹出右边的括号，判断栈里边最后入的那个元素和目前的右边括号是否相同。如果不同就返回false。有种可能是入栈很多左括号，右括号个数小于左括号个数，所以最后也要判断一下栈是否为空，如果是空说明左右括号个数正好匹配。

public class Solution {
    public boolean isValid(String s) {
        if(s == null || (s.length() & 1) == 1){
            return false;
        }
        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();
    }
}

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Python解法

二刷，Python，使用的也是栈。

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for c in s:
            if not stack:
                stack.append(c)
            else:
                if c in ['(', '[', '{']:
                    stack.append(c)
                else:
                    top = stack.pop()
                    if (top == '(' and c != ')') or \
                        (top == '[' and c != ']') or \
                        (top == '{' and c != '}'):
                        return False
        return not stack

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发

25 4 0
文章推荐： 6. Zigzag Conversion Z 字形变换
文章推荐： 9. Palindrome Number 回文数
文章推荐： 34. Find First and Last Position of Element in Sorted Array 在排序数组中查找元素的第一个和最后一个位置
大佬之路
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com