当前位置：首页 > article >正文

【练习】力扣热题100 有效的括号

article 2025/1/15 7:52:47

题目

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([])”

输出：true

来源：力扣热题100 有效的括号

题解

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        stack<char> st;
        for(int i = 0; i < n; i ++)
        {
            if(s[i] == '(' || s[i] == '[' || s[i] == '{')
                st.push(s[i]);
            else
            {
                if(st.empty())
                    return false;
                if(st.top() == '(' && s[i] != ')')
                    return false; 
                if(st.top() == '[' && s[i] != ']')
                    return false; 
                if(st.top() == '{' && s[i] != '}')
                    return false; 
                st.pop();
                if(st.empty() && i == n - 1)
                    return true;
            }
        }
        return false;
    }
};

题解（优化）

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};

以下是代码的详细分析：

`pairs.count(ch)` 的作用

pairs.count(ch) 是 C++ 中 unordered_map 的成员函数，用于检查键 ch 是否存在于哈希表 pairs 中。
返回值：
- 如果 ch 是 pairs 的键（即 ch 是右括号 )、] 或 }），则返回 1。
- 如果 ch 不是 pairs 的键（即 ch 是左括号或其他字符），则返回 0。

代码逻辑分析：

检查字符串长度：
```
int n = s.size();
if (n % 2 == 1) {
    return false;
}
```
- 如果字符串的长度是奇数，则括号一定无法完全匹配，直接返回 false。
定义括号映射：
```
unordered_map<char, char> pairs = {
    {')', '('},
    {']', '['},
    {'}', '{'}
};
```
- 使用一个哈希表 pairs 来存储右括号和对应的左括号的映射关系。
- 例如，')' 对应 '('，']' 对应 '['，'}' 对应 '{'。
使用栈进行匹配：
```
stack<char> stk;
for (char ch: s) {
    if (pairs.count(ch)) {
        if (stk.empty() || stk.top() != pairs[ch]) {
            return false;
        }
        stk.pop();
    }
    else {
        stk.push(ch);
    }
}
```
- 遍历字符串中的每个字符：
  - 如果当前字符是右括号（即 pairs.count(ch) 为真）：
    - 检查栈是否为空，或者栈顶元素是否与当前右括号对应的左括号匹配。
    - 如果不匹配，则返回 false。
    - 如果匹配，则将栈顶元素弹出。
  - 如果当前字符是左括号，则将其压入栈中。
检查栈是否为空：
```
return stk.empty();
```
- 如果栈为空，说明所有括号都匹配成功，返回 true。
- 如果栈不为空，说明有未匹配的左括号，返回 false。

举例说明：

假设输入字符串为 s = "()[]{}"，运行过程如下：

初始化：
- stk = []（空栈）。
遍历字符：
- ch = '('：是左括号，压入栈中。stk = ['(']。
- ch = ')'：是右括号，检查栈顶元素 '(' 是否匹配。匹配，弹出栈顶元素。stk = []。
- ch = '['：是左括号，压入栈中。stk = ['[']。
- ch = ']'：是右括号，检查栈顶元素 '[' 是否匹配。匹配，弹出栈顶元素。stk = []。
- ch = '{'：是左括号，压入栈中。stk = ['{']。
- ch = '}'：是右括号，检查栈顶元素 '{' 是否匹配。匹配，弹出栈顶元素。stk = []。
最终检查：
- 栈为空，返回 true。

时间复杂度：

O(n)，其中 n 是字符串的长度。每个字符只会被压入栈和弹出栈一次。

空间复杂度：

O(n)，在最坏情况下（例如全是左括号），栈的大小为 n/2。

代码的改进建议：

使用数组代替哈希表：

由于括号字符的 ASCII 值是连续的，可以使用数组代替哈希表来存储映射关系，进一步提高性能。

改进后的代码：

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        char pairs[256] = {0}; // 初始化所有字符映射为 0
        pairs[')'] = '(';
        pairs[']'] = '[';
        pairs['}'] = '{';

        stack<char> stk;
        for (char ch: s) {
            if (pairs[ch]) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};