解题思路

这是一道经典的括号匹配问题，可以使用栈来解决：

  1. 遍历字符串中的每个字符
  2. 遇到左括号 ([( 时，将其压入栈中
  3. 遇到右括号 )] 时，检查栈顶元素是否与当前右括号匹配
    • 如果栈为空或栈顶元素不匹配，返回false
    • 如果匹配，弹出栈顶元素继续处理
  4. 最后检查栈是否为空，为空则表示所有括号都匹配

代码

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

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '[' || c == '(') {
            st.push(c);
        } else if (c == ']' || c == ')') {
            if (st.empty()) return false;
            if (c == ']' && st.top() != '[') return false;
            if (c == ')' && st.top() != '(') return false;
            st.pop();
        }
    }
    return st.empty();
}

int main() {
    string s;
    cin >> s;
    cout << (isValid(s) ? "true" : "false") << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '[' || c == '(') {
                stack.push(c);
            } else if (c == ']' || c == ')') {
                if (stack.isEmpty()) return false;
                if (c == ']' && stack.peek() != '[') return false;
                if (c == ')' && stack.peek() != '(') return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(isValid(s));
    }
}

def is_valid(s: str) -> bool:
    stack = []
    for c in s:
        if c in ['[', '(']:
            stack.append(c)
        elif c in [']', ')']:
            if not stack:
                return False
            if c == ']' and stack[-1] != '[':
                return False
            if c == ')' and stack[-1] != '(':
                return False
            stack.pop()
    return len(stack) == 0

s = input()
print(str(is_valid(s)).lower())

算法及复杂度

  • 算法：栈
  • 时间复杂度： - 其中 是字符串长度，需要遍历每个字符一次
  • 空间复杂度： - 最坏情况下，所有字符都是左括号，需要将它们全部压入栈中