20_有效的括号

猿柒

8个月前更新

20_有效的括号

【问题描述】

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例一：
输入：s = "()"
输出：true

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

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

示例四：
输入：s = "([])"
输出：true

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

【算法设计思想】

在解决本题时，我们要使用一种类似于键值对的数据结构，要确保左右括号的对应关系。在Python中我们可以直接使用内置的字典数据类型，在Java中我们可以使用HashMap类，在C++中我们可以使用STL中的unordered_map来实现，在什么都没有的C语言中我们可以直接自己定义一个pairs函数用来实现这种对应关系。然后我们依次遍历给定的字符串s，如果碰到了左括号，那么我们把它加入到栈中，如果碰到了右括号，那么我们调用这种对应关系，然后判断栈顶的元素和其是否匹配，如果匹配，那么我们继续遍历，只要有一个不匹配，那么我们直接返回false即可。最后我们看一下栈是否为空，即可得出结论。

注意：

Java中和C++中各种数据结构的调用

【算法描述】

Python：

class Solution:
    def isValid(self, s: str) -> bool:
        # 定义括号对应关系的字典，右括号为键，左括号为值
        brackets = {')': '(', ']': '[', '}': '{'}
        
        # 初始化一个空栈，用于存放左括号
        stack = []
        
        # 遍历字符串中的每个字符
        for char in s:
            # 如果字符是左括号，将其压入栈中
            if char in brackets.values():
                stack.append(char)
            # 如果字符是右括号，检查匹配情况
            elif char in brackets:
                # 当栈为空或栈顶元素不匹配当前右括号时，返回False
                if not stack or brackets[char] != stack[-1]:
                    return False
                # 如果栈顶元素匹配当前右括号，弹出栈顶元素
                stack.pop()
        
        # 遍历结束后，检查栈是否为空
        # 如果栈为空，说明所有括号成功匹配；否则返回False
        return not stack

C++:

class Solution {
public:
    bool isValid(const std::string& s) {
        // 定义括号对应关系的 unordered_map，右括号为键，左括号为值
        std::unordered_map<char, char> brackets = {
            {')', '('},  // 右括号 ')' 对应左括号 '('
            {']', '['},  // 右括号 ']' 对应左括号 '['
            {'}', '{'}   // 右括号 '}' 对应左括号 '{'
        };

        // 初始化一个空栈，用于存放左括号
        std::stack<char> stack;

        // 遍历字符串中的每个字符
        for (char elem : s) {
            // 如果字符是左括号，将其压入栈中
            if (elem == '(' || elem == '[' || elem == '{') {
                stack.push(elem);
            }
            // 如果字符是右括号，检查匹配情况
            else if (brackets.count(elem)) {
                // 当栈为空或栈顶元素不匹配当前右括号时，返回 false
                if (stack.empty() || stack.top() != brackets[elem]) {
                    return false;
                }
                // 如果栈顶元素匹配当前右括号，弹出栈顶元素
                stack.pop();
            }
            // 如果字符既不是左括号也不是右括号，返回 false（可以选择忽略或处理非法字符）
            else {
                return false;
            }
        }

        // 遍历结束后，检查栈是否为空
        // 如果栈为空，说明所有括号成功匹配；否则返回 false
        return stack.empty();
    }
};

Java：

class Solution {
    public boolean isValid(String s) {
        // 获取字符串的长度
        int n = s.length();
        
        // 如果长度是奇数，括号不可能成对匹配，直接返回 false
        if (n % 2 == 1) {
            return false;
        }

        // 定义一个 HashMap 来存储括号的配对关系
        // 右括号为键，左括号为值
        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)) {
                // 如果栈为空，或栈顶的左括号不匹配当前的右括号，返回 false
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }

                // 如果栈顶元素匹配当前右括号，弹出栈顶元素
                stack.pop();
            } 
            // 如果字符是左括号，将其压入栈中
            else {
                stack.push(ch);
            }
        }
        
        // 遍历结束后，检查栈是否为空
        // 如果栈为空，说明所有的括号都成功匹配；否则返回 false
        return stack.isEmpty();
    }
}

C：

/**
 * 根据给定的右括号字符返回对应的左括号字符。
 * @param ch 一个右括号字符。
 * @return 对应的左括号字符，如果不存在则返回0。
 */
char pairs(char ch)
{
    if (ch == ')')
        return '(';
    if (ch == ']')
        return '[';
    if (ch == '}')
        return '{';
    return 0;
}

/**
 * 检查给定的字符串中的括号是否正确匹配。
 * @param s 包含括号的字符串。
 * @return 如果括号正确匹配，则返回true；否则返回false。
 */
bool isValid(char *s)
{
    int n = strlen(s);
    // 如果字符串长度为奇数，则括号无法完全匹配
    if (n % 2 == 1)
    {
        return 0;
    }
    char stack[n + 1];
    int top = 0;

    for (int i = 0; i < n; i++)
    {
        char ch = pairs(s[i]);
        if (ch)
        {
            // 如果当前字符是右括号，检查它是否与栈顶的左括号匹配
            if (top == 0 || stack[top - 1] != ch)
            {
                return 0;
            }
            top--;
        }
        else
        {
            // 如果当前字符是左括号，将其压入栈顶
            stack[top++] = s[i];
        }
    }
    // 如果栈为空，说明所有括号都正确匹配
    return top == 0;
}

评分

欢迎为Ta评分