LeetCode: 20. Valid Parentheses（有效字符串）-蒲公英云

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

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

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

相关文章：

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

文章目录

一.题目描述

二. 实现方式 1

java实现方式
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