【算法题解】14. 有效的括号

这是一道简单题。

来自：https://leetcode.cn/problems/valid-parentheses/solutions/

题目

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

有效字符串需满足：

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

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

3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

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



示例 2：
输入：s = "()[]{}"
输出：true



示例 3：
输入：s = "(]"
输出：false



提示：







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

























解法：使用栈的特性












有效字符串可以使用 栈的特性（先进后出，后进先出）来解题。



1.  当遇到 左括号（‘(’，‘[’，‘{’）时入栈。
2.  当遇到 右括号（‘)’，‘]’，‘}’）时：



若此时栈为空，直接返回false。因为前面没有和这个右括号匹配的左括号。


若此时栈顶元素和当前右括号不是一对，直接返回false。


若此时栈顶元素和当前右括号成对，栈顶元素出栈，然后继续遍历字符串中的下一个元素。



3.  当将整个字符串遍历完成后：



如果此时栈为空，返回true。


如果此时栈不空，返回false。此时栈中的前括号没有对应的后括号与之成对。





以有效的括号 ‘([]{})’为例动图展示：








01



Java 代码实现








使用 HashMap 存放成对的 前后括号，使用时可以直接根据 后括号 获取到与之对应的 前括号。



class Solution {
    public boolean isValid(String s) {

        if(s.length() % 2 != 0){
            return false;
        }

        Map<Character, Character> pairs = new HashMap<>();
        pairs.put(')', '(');
        pairs.put(']', '[');
        pairs.put('}', '{');

        Deque<Character> stack = new LinkedList<>();

        for(char c : s.toCharArray()){
            if(pairs.containsKey(c)){
                if(stack.isEmpty() || stack.peek() != pairs.get(c)){
                    return false;
                }
                stack.pop();
            }else{
                stack.push(c);
            }
        }

        return stack.isEmpty();

    }
}








02



Go 代码实现








因为Go语言本身没有实现栈这个数据结构，所以我们用切片代替，思路是一样的。




func isValid(s string) bool {
    n := len(s)
    if n % 2 != 0 {
        return false
    }
    pairs := map[byte]byte{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    stack := []byte{}
    for i := 0; i < n; i++ {
        if pairs[s[i]] > 0 {
            if len(stack) == 0 || stack[len(stack)-1] != pairs[s[i]] {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, s[i])
        }
    }
    return len(stack) == 0
}








03



复杂度分析








时间复杂度：，N 为字符串长度。
空间复杂度：，N 为字符串长度。paris 空间复杂度为常数，stack 空间复杂度为 N。











点个在看你最好看







原文始发于微信公众号（i余数）：【算法题解】14. 有效的括号

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/193991.html

【算法题解】14. 有效的括号

相关推荐

发表回复

分享到: