使由 '{', '}', '[', ']', '(', ')' 组成的括号字符串的最小加法有效

Question

这个问题是对熟悉的堆栈问题（https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/）的补充，我们必须返回最小加法次数以使括号字符串有效. 但是这个问题只包含'('和')'。如果我们将该问题扩展到其他类型的括号，如“[”、“]”、“{”、“}”，会发生什么。我刚刚在与朋友的讨论中遇到了这个问题，需要关于如何处理的帮助。

例如： [[[{{}]]){)}) -> [[[{{ } }]] ] ( ){ ( )} ( ) 在这种情况下，答案是 5 次添加以使其有效。

我想不出合适的方法。我考虑的两种方法是：

1. 与普通问题类似，我们在浏览字符串时将开始类型 '(', '{', '[' 推送到堆栈，如果我们找到结束类型 ')', '}', ']' 我们检查在栈顶，如果它们相互补充，我们弹出并继续，否则我们增加计数器并继续而不弹出。遍历字符串后，我们将答案输出为计数器和堆栈大小的总和。在这种方法中，上面的示例将不起作用，因为额外的 '{' 会破坏该方法。

2. 另一种方法类似于上面的即。我们压入括号的开始类型，如果我们找到一个结束类型并且堆栈的顶部与它互补，我们弹出并继续字符串，否则我们将弹出直到我们得到匹配的字符串，并且每次弹出我们增加计数器。遍历字符串后，总值是计数器和堆栈大小的总和。但这不适用于 {{{{]}}}} 这样的情况，其中字符 ']' 会弹出所有内容并增加答案。

我也在考虑将这些结合起来，更像是一个动态规划，我们将最大程度地看到最高值，或者看到堆栈中的匹配项或堆栈是否为空。但我不确定这两种情况是否是唯一需要考虑的情况。

Answer 1

解释

我们将逐个字符处理输入字符串，并更新迄今为止遇到的括号的某些信息。对于每种括号类型，创建一个堆栈来保留未补偿的左括号的位置。基本上，它表示需要多少个当前类型的右括号才能使字符串在检查时有效。

对于输入的每个括号，执行以下操作之一：

1. 如果括号是左括号（任何类型），只需将其位置添加到相应的堆栈中即可。
2. 否则，它是一个右括号。如果堆栈中没有左括号，只需增加结果总和 - 不平衡的右括号可以立即得到补偿。
3. 最后，它是一个右括号，并且当前类型的堆栈中有左括号。因此，将位于同一类型的最后一个左括号和当前括号之间的所有其他类型的不平衡括号的数量相加！不要忘记从堆栈中删除匹配的元素。

最后，将每个堆栈的剩余大小添加到结果总和中，因为每种类型的左括号可能仍然不平衡。

代码

我用C++创建了一个简单的解决方案，但如果需要，它可以轻松转换为任何其他语言：

#include <iostream>
#include <stack>
#include <unordered_map>

bool isOpeningBracket(char bracket) {
    return bracket == '(' || bracket == '[' || bracket == '{';
}

int main() {
    std::string line;
    std::cin >> line;
    std::unordered_map<char, char> closingToOpeningBracket = {
            {')', '('},
            {']', '['},
            {'}', '{'}
    };

    std::unordered_map<char, std::unique_ptr<std::stack<uint64_t>>> bracketsMap;
    bracketsMap['{'] = std::make_unique<std::stack<uint64_t>>();
    bracketsMap['['] = std::make_unique<std::stack<uint64_t>>();
    bracketsMap['('] = std::make_unique<std::stack<uint64_t>>();
    uint64_t addOperations = 0;

    for(auto i = 0; i < line.size(); i++) {
        auto bracket = line[i];
        bool isOpening = isOpeningBracket(bracket);

        auto key = bracket;
        if (!isOpening) {
            key = closingToOpeningBracket[bracket];
        }
        auto &bracketStack = bracketsMap[key];
        if (isOpening) {
            bracketStack->push(i);
        } else if (!bracketStack->empty()) {
            auto openingBracketPosition = bracketStack->top();
            bracketStack->pop();

            for (auto & [key, value] : bracketsMap) {
                while (!value->empty() && value->top() > openingBracketPosition) {
                    addOperations++;
                    value->pop();
                }
            }
        } else {
            addOperations++;
        }
    }

    for (auto & [key, value] : bracketsMap) {
        addOperations += value->size();
    }

    std::cout << addOperations << "\n";

    return 0;
}

时间和空间复杂度

该解的时间和空间复杂度为O(n)。