题解 | #完成括号匹配#

解题思路

理解合法括号序列：
- 空串是合法的。
- 如果 X 和 Y 是合法的括号序列，则 XY 也是合法的。
- 如果 X 是合法的括号序列，则 ( + X + ) 也是合法的。
操作：
- 统计当前字符串中左括号 ( 和右括号 ) 的数量。
- 根据数量差异，计算需要添加的左括号和右括号的数量。

代码

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

string generate_valid_parentheses(string s) {
    int left_needed = 0, right_needed = 0;

    for (char c : s) {
        if (c == '[') {
            left_needed++;
        } else if (c == ']') {
            if (left_needed > 0) {
                left_needed--;
            } else {
                right_needed++;
            }
        }
    }

    return string(right_needed, '[') + s + string(left_needed, ']');
}

int main() {
    string s;
    cin >> s;
    cout << generate_valid_parentheses(s) << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static String generateValidParentheses(String s) {
        int leftNeeded = 0, rightNeeded = 0;

        for (char c : s.toCharArray()) {
            if (c == '[') {
                leftNeeded++;
            } else if (c == ']') {
                if (leftNeeded > 0) {
                    leftNeeded--;
                } else {
                    rightNeeded++;
                }
            }
        }

        // 使用 StringBuilder 来构建结果字符串
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < rightNeeded; i++) {
            result.append('[');
        }
        result.append(s);
        for (int i = 0; i < leftNeeded; i++) {
            result.append(']');
        }

        return result.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        System.out.println(generateValidParentheses(s));
    }
}

def generate_valid_parentheses(s: str) -> str:
    left_needed = 0  # 需要的左括号数量
    right_needed = 0  # 需要的右括号数量

    for char in s:
        if char == '[':
            left_needed += 1
        elif char == ']':
            if left_needed > 0:
                left_needed -= 1
            else:
                right_needed += 1

    return '[' * right_needed + s + ']' * left_needed

if __name__ == "__main__":
    s = input()
    print(generate_valid_parentheses(s))

算法及复杂度

算法：统计括号数量并生成合法括号序列。
时间复杂度： $\mathcal{O}(n)$
空间复杂度： $\mathcal{O}(n)$