LeetCode: 20. Valid Parentheses（有效字符串）

清疚 2022-11-27 08:59 79阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录**

一.题目描述

二. 实现方式 1

1. java实现方式

2. python实现方式

三.实现方式2

1.java实现方式

2 pyhton实现方式

--------------------

## ** 一.题目描述** ##

定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
    
    有效字符串需满足：
    
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    注意空字符串可被认为是有效字符串。
    
    示例 1:
    
    输入: "()"
    输出: true
    示例 2:
    
    输入: "()[]{}"
    输出: true
    示例 3:
    
    输入: "(]"
    输出: false
    示例 4:
    
    输入: "([)]"
    输出: false
    示例 5:
    
    输入: "{[]}"
    输出: true

## 二. 实现方式 1  ##

###      1. java实现方式 ###

/**
         * 判断是否是有效字符串
         *
         * @param s 字符串
         * @return 布尔值
         */
        public boolean isValid(String s) {
            if (s.length() % 2 == 0) {
                return false;
            }
            Deque<Character> stack = new LinkedList<>();
            for (char ch : s.toCharArray()) {
                if (ch == '{' || ch == '(' || ch == '[') {
                    stack.push(ch);
                } else if (ch == ']') {
                    if (!stack.isEmpty() && stack.pop() != '[') {
                        return false;
                    }
                } else if (ch == ')') {
                    if (!stack.isEmpty() && stack.pop() != '(') {
                        return false;
                    }
                } else {
                    if (!stack.isEmpty() && stack.pop() != '{') {
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }

###   2. python实现方式    ###

def is_valid(s: str) -> bool:
        """
            判断括号是否匹配
        Args:
            s:括号字符串
        Returns:
            布尔值
        """
        if len(s) % 2 == 1:
            return False
        stack = []
        for ch in s:
            if ch == '[' or ch == '(' or ch == '{':
                stack.append(ch)
            elif ch == ']':
                if not stack or stack.pop() != '[':
                    return False
            elif ch == ')':
                if not stack or stack.pop() != '(':
                    return False
            else:
                if not stack or stack.pop() != '{':
                    return False
        return not stack

时间复杂度:O(n)

空间复杂度：O(n)

--------------------

## 三.实现方式2 ##

### 1.java实现方式 ###

/**
         * 判断是否是有效字符串
         *
         * @param s 字符串
         * @return 布尔值
         */
        public boolean isValid2(String s) {
            Deque<Character> stack = new LinkedList<>();
            for (char ch : s.toCharArray()) {
                if (ch == '{') {
                    stack.push('}');
                } else if (ch == '(') {
                    stack.push(')');
                } else if (ch == '[') {
                    stack.push(']');
                } else if (stack.isEmpty() || ch != stack.pop()) {
                    return false;
                }
            }
            return stack.isEmpty();
        }

##  2 pyhton实现方式 ##

def is_valid2(s: str) -> bool:
        """
            判断括号是否匹配
        Args:
            s:括号字符串
        Returns:
            布尔值
        """
        stack = []
        for ch in s:
            if ch == '[':
                stack.append(']')
            elif ch == '(':
                stack.append(')')
            elif ch == '{':
                stack.append('}')
            elif not stack or ch != stack.pop():
                return False
        return not stack

时间复杂度:O(n)

空间复杂度：O(n)

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201