20、有效的括号

leetcode

Created At : 2020-07-26 00:19

Count:717 Views 👀 :

Comment:

示例 1:
示例 2:
示例 3:
示例 4:
示例 5:

题解

1、栈的应用
哈希表

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

题解

1、栈的应用

通过栈push 左括号，遇到右括号，就pop

// java
class Solution {
    public boolean isValid(String s) {
        // 异常处理
        if (s.length() == 0) return true;
        if (s.length()%2 == 1) return false;
        LinkedList<Character> sk = new LinkedList<>();
        sk.push(s.charAt(0)); // 将第一个
        for (int i = 1;i < s.length();i++) {
            char tmp = s.charAt(i);
            // 逐个出栈判断
            if (tmp == ')' && sk.peek() == '(') {
                sk.pop();
                continue;
            }
            if (tmp == '}' && sk.peek() == '{') {
                sk.pop();
                continue;
            }
            if (tmp == ']' && sk.peek() == '[') {
                sk.pop();
                continue;
            }
            // 入栈
            sk.push(tmp);
        }
        return sk.isEmpty();
    }
}

// C++
class Solution {
public:
    // 栈的应用
    bool isValid(string s) {
        // 异常处理
        if (s.length() == 0) return true;
        if (s.length()%2 == 1) return false;
        stack<char> sk;
        sk.push(s[0]);// 将第一个
        for (int i = 1;i < s.length();i++) {
            // 逐个出栈判断
            if (s[i] == ')' && sk.top() == '(') {
                sk.pop();
                continue;
            }
            if (s[i] == '}' && sk.top() == '{') {
                sk.pop();
                continue;
            }
            if (s[i] == ']' && sk.top() == '[') {
                sk.pop();
                continue;
            }
            // 入栈
            sk.push(s[i]);
        }
        return sk.empty();
    }
};

哈希表

建立右括号对左括号的映射，遇到右括号就检查合法性，否则push到栈中。

每个算法题都应该有一个算法实施的语言描述，因为这样的过程成为之数学建模。也可以说明伪代码比真正的实现代码更重要！！！

建立右括号映射左括号的map，用于查找左括号
创建一个栈对象，
遍历字符串的字符
- 遇到右括号，匹配栈顶左括号（条件判断的失败case优先策略，用else处理成功case)
  - 匹配失败，返回false
  - 匹配成功，继续遍历字符
- 遇到左括号，加入栈中
最后以栈是否为空作为是否合法的判断

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        // 哈希表，存储映射关系
        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {// 遇到右括号
                // 判断合法性
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com