优先级的括号匹配

约 1192 字大约 4 分钟

栈中等腾讯

2024-12-26

⭐️ 题目日期：

腾讯 - 2024/12/17

🌳 题目描述：

给定一个只包括 '('，')'，'['，']'， '{'，'}' 的字符串 s ，括号的优先级排序由高到低依次为()，[]，{}，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
内层括号的优先级不低于外层括号。

示例 1：
输入：{[()]}
输出：True
解释：确保内层括号优先级不低于外层，() 优先级最高，在最里层，随后是 []，最外层是优先级最低的 {}，符合条件

示例 2：
输入：([{}])
输出：False
解释：[优先级低于(，不符合匹配规则

🕵🏽 面试评估：

这道题主要考察候选人对栈的理解与运用，能够采用其后进先出的特性，并且考虑到括号匹配中的优先级顺序和不同类型括号的配对规则，解决这种类型的括号配对问题。

🧗难度系数：

⭐️ ⭐️ ⭐️

📝思路分析：

要判断字符串中的括号是否在给定的规则下完成匹配，需要从左到右依次扫描每一个括号，在一个嵌套型的括号组合里（如 {[()]})，后访问的括号先完成匹配（{[() 中 () 先完成匹配），这个匹配的规律刚好满足栈的后进先出的操作特性，所以我们可以尝试用栈来解决这道题。

我们将所有满足优先级顺序的左括号加入栈中，也就是说如果访问到一个左括号，它的优先级低于栈顶左括号的优先级，说明当前括号组合里层的括号优先级低于外层，不满足括号优先级的匹配规则，直接返回 false；

当加入到栈中的左括号满足优先级顺序时，每访问到一个右括号时，如果能根栈顶的左括号形成配对，则当前括号对匹配成功，将栈顶的元素出栈，继续匹配剩余栈中的左括号；如果当前的右括号不能形成配对，返回 false;

遍历完字符串s后，如果栈为空，表示所有开括号都已经匹配成功，返回 true如果栈不为空，说明有未匹配的左括号，返回false

以案例 2 为例，我们来分析一下具体的过程。
输入：([{}])，优先级：{[(
输出：False

字符串长度为偶数，那么我们根据传递的优先级字符串{[( 建立映射，此时 map 为：
{ -> 0
[ -> 1
( -> 2
遍历字符串。
1. 首先是字符 (，是左括号，此时栈为空，直接压入栈中，此时栈的状态为：["("]
2. 字符 [，是左括号，此时栈顶是 (，优先级为 2，[ 的优先级为 1，由于 1 < 2，因此不满足条件，[ 的优先级低于 (，他不能置于 ( 的内层，返回 false

💻代码（Java、Python、C++）：

Java

 public boolean isValid(String s, String priority) {
    if (s.length() % 2 == 1) {
        return false;
    }

    // 存不同括号的优先级 <key, value> = <括号，优先级的大小>
    Map<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < priority.length(); i++) {
        map.put(priority.charAt(i), i);
    }
    
    Deque<Character> stack = new LinkedList<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '{' || c == '[') {
            if (!stack.isEmpty() && map.get(c) < map.get(stack.peekLast())) {
                return false;
            }
            stack.offerLast(c);
        } else if (!stack.isEmpty() && isValidPair(stack.peekLast(), c)) {
            stack.pollLast();
        } else {
            return false;
        }
    }

    return stack.isEmpty();
}

private boolean isValidPair(char c1, char c2) {
    return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}') || (c1 == '[' && c2 == ']');
}

Python

from collections import deque

def isValid(s: str, priority: str) -> bool:
    if len(s) % 2 == 1:
        return False

    # 存不同括号的优先级 <key, value> = <括号，优先级的大小>
    map = {priority[i]: i for i in range(len(priority))}
    stack = deque()

    for c in s:
        if c in "({[":
            if stack and map[c] < map[stack[-1]]:
                return False
            stack.append(c)
        elif stack and isValidPair(stack[-1], c):
            stack.pop()
        else:
            return False

    return not stack

def isValidPair(c1: str, c2: str) -> bool:
    return (
        (c1 == "(" and c2 == ")")
        or (c1 == "{" and c2 == "}")
        or (c1 == "[" and c2 == "]")
    )

C++

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    bool isValidPair(char c1, char c2) {
        return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}') ||
               (c1 == '[' && c2 == ']');
    }

    bool isValid(string s, string priority) {
        if (s.length() % 2 == 1) {
            return false;
        }

        // 存不同括号的优先级 <key, value> = <括号，优先级的大小>
        unordered_map<char, int> map;
        for (int i = 0; i < priority.length(); i++) {
            map[priority[i]] = i;
        }

        stack<char> stk;
        for (char c : s) {
            if (c == '(' || c == '{' || c == '[') {
                if (!stk.empty() && map[c] < map[stk.top()]) {
                    return false;
                }
                stk.push(c);
            } else if (!stk.empty() && isValidPair(stk.top(), c)) {
                stk.pop();
            } else {
                return false;
            }
        }

        return stk.empty();
    }
};

🚵🏻复杂度分析：

时间复杂度：O(n)，其中 n 为字符串的长度

空间复杂度：O(n)，空间主要来自栈存储左括号，由于只有 3 种括号，哈希表中只有 3 对 <key, value>, 哈希表的空间使用为 O(1), 所以总的空间复杂度为 O(n)