解题思路

这是一个括号匹配和移除操作的计数问题。对于每个左括号，我们需要找到其对应的所有可能的右括号。

关键点：

  1. 每次移除操作包含两步：

    • 移除第一个左括号（固定的）
    • 移除一个合法的右括号（有多种选择）

  2. 合法性判断：

    • 移除括号后，剩余的序列必须是合法的括号序列
    • 需要保持左右括号的平衡

代码

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

int main() {
    string s;
    while (cin >> s) {
        int n = s.length();
        long long result = 1;
        int leftCount = 0;
        
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') {
                leftCount++;
            } else {
                result *= leftCount;
                leftCount--;
            }
        }
        
        cout << result << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.next();
            int n = s.length();
            long result = 1;
            int leftCount = 0;
            
            for (int i = 0; i < n; i++) {
                if (s.charAt(i) == '(') {
                    leftCount++;
                } else {
                    result *= leftCount;
                    leftCount--;
                }
            }
            
            System.out.println(result);
        }
        sc.close();
    }
}

while True:
    try:
        s = input()
        n = len(s)
        result = 1
        left_count = 0
        
        for c in s:
            if c == '(':
                left_count += 1
            else:
                result *= left_count
                left_count -= 1
                
        print(result)
    except:
        break

算法及复杂度

  • 算法：贪心计数
  • 时间复杂度：，其中 是字符串长度
  • 空间复杂度：，只使用常数额外空间