leetcode20：有效的括号

题目链接

leetcode

题目描述

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

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

C++ 代码

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

/*
    栈是一种先进后出的数据结构，处理括号问题尤其有用。
	遇到左括号就入栈，遇到右括号就去栈中找最近的左括号，看是否匹配。

    时间复杂度：O(n)
        其中 n 是字符串的长度。
        遍历字符串一次，对于每个字符，操作的时间复杂度是 O(1)。
    空间复杂度：O(n)
        在最坏的情况下，字符串只包含右括号，栈将包含所有 n 个字符。
*/
class Solution_0 {
public:
    bool isValid(string s) {
        stack<char> stk;
        for (const char& c : s) {
            if (c == '(' || c == '{' || c == '[') {
                stk.push(c);
            } else if (c == ')') {
                if (stk.empty() || stk.top() != '(') {
                    return false;
                }
                stk.pop();
            } else if (c == '}') {
                if (stk.empty() || stk.top() != '{') {
                    return false;
                }
                stk.pop();
            } else if (c == ']') {
                if (stk.empty() || stk.top() != '[') {
                    return false;
                }
                stk.pop();
            }
        }
        return stk.empty();
    }
};

/*
    思路同上，代码更简洁。
*/
class Solution {
public:
    bool isValid(string s) {
        stack<int> stk;
        for (const char& c : s) {
            if (c == '(' || c == '{' || c == '[') {
                stk.push(c);
            } else if (c == ')' || c== '}' || c == ']') {
                // 最近的左括号不匹配
                if (stk.empty() || stk.top() != getLeft(c)) {
                    return false;
                }
                stk.pop();
            }
        }
        // 所有的左括号是否都匹配
        return stk.empty();
    }

    char getLeft(char c) {
        if (c == ')') return '(';
        else if (c == '}') return '{';
        else if (c == ']') return '[';
        return ' ';
    }
};

int main() {
    Solution solution;
    vector<string> testStrings = {
        "()",
        "(]",
        "([])",
        "()[]{}"
    };

    for (const string& str : testStrings) {
        cout << "Is '" << str << "' a valid parenthesis string? " << (solution.isValid(str) ? "Yes" : "No") << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   栈的使用：
       使用一个栈来存储左括号。
       遍历字符串，遇到左括号时压入栈，遇到右括号时检查栈顶是否有对应的左括号。
   括号匹配：
       如果栈为空但遇到右括号，说明没有对应的左括号，返回 false。
       如果栈顶的左括号与当前的右括号匹配，弹出栈顶元素。
       如果不匹配，返回 false。
   最终判断：
       如果遍历结束后栈为空，说明所有括号都匹配，返回 true。
       如果栈不为空，说明有未匹配的左括号，返回 false。

    时间复杂度：O(n)
        其中 n 是字符串的长度。
        遍历字符串一次，每个字符的操作（压栈或弹栈）的时间复杂度为 O(1)。
    空间复杂度：O(n)
        在最坏的情况下，字符串只包含右括号，栈将包含所有 n 个字符。
*/
// isValid 判断括号字符串是否有效
func isValid(s string) bool {
	stack := []rune{}
	pairs := map[rune]rune{
		')': '(',
		']': '[',
		'}': '{',
	}
    
    for _, c := range s {
        if _, ok := pairs[c]; ok {
            // 如果是右括号，检查栈顶是否为左括号
            if len(stack) == 0 || stack[len(stack)-1] != pairs[c] {
                return false
            }
            // 弹出栈顶元素
            stack = stack[:len(stack)-1]
        } else {
            // 如果是左括号，则入栈
            stack = append(stack, c)
        }
    }
    // 如果栈为空，说明所有括号都匹配
    return len(stack) == 0
}

func main() {
	// 测试用例
	testCases := []struct {
		s        string
		expected bool
	}{
		{"()", true},
		{"()[]{}", true},
		{"(]", false},
		{"([)]", false},
		{"", true},
		{"(", false},
		{")", false},
	}

	for i, tc := range testCases {
		result := isValid(tc.s)
		fmt.Printf("Test Case %d: Input: s = %q\n", i+1, tc.s)

		if result == tc.expected {
			fmt.Printf("Output: %v, PASS\n", result)
		} else {
			fmt.Printf("Output: %v, FAIL (Expected: %v)\n", result, tc.expected)
		}
	}
}