为何求解字符串最小合规成本的代码无法适配大型测试用例？

给定仅包含{或}的字符串STR，当所有括号平衡时（每个左括号右侧对应一个右括号），STR被称为合规字符串。例如"{}{}"、"{{}}"、"{{}{}}"是合规字符串，而"}{}"、"{}}{{}"、"{{}}}{"不是。需通过转换括号（将{转为}或反之，每次操作成本为1）使STR合规，求最小成本。

用户实现代码 #

int solve(string str, stack<char>& s, int i) {
    if (i >= str.length()) {
        return 0;
    }
    if (str[i] == '{') {
        s.push('{');
    } else {
        if (!s.empty() && s.top() == '{') {
            s.pop();
        } else {
            s.push('}');
        }
    }
    return solve(str, s, i + 1);
}

int valid(stack<char>& s) {
    int count = 0;
    while (!s.empty()) {
        char x = s.top();
        s.pop();
        if (!s.empty()) {
            char y = s.top();
            s.pop();
            if (x == y) {
                count++;
            } else {
                count += 2;
            }
        }
    }
    return count;
}

int findMinimumCost(string str) {
    if ((str.length() % 2) != 0) {
        return -1;
    }
    stack<char> s;
    solve(str, s, 0);
    if (s.empty()) {
        return 0;
    } else {
        return valid(s);
    }
}

原实现思路 #

通过solve函数递归遍历字符串处理括号匹配，无法匹配的括号存入栈；若栈非空则调用valid函数计算转换成本：每次取出两个栈顶元素，若相同则成本+1，不同则+2。该代码在大型测试用例中失败，需优化至最优解。

问题分析与优化方案 #

原代码缺陷 #

1. 递归栈溢出：solve函数用递归遍历字符串，当字符串长度极大时，会触发程序栈溢出，这是大型测试用例失败的核心原因。
2. 空间效率低下：使用栈存储未匹配括号，对于超长字符串会占用大量额外内存。

最优解法思路 #

无需递归和栈，仅通过两个计数变量即可完成计算：

• 维护open（未匹配的左括号数）和close（未匹配的右括号数）两个变量。
• 遍历字符串：
  • 遇到{时，open加1；
  • 遇到}时，若open > 0则open减1（匹配成功），否则close加1（无左括号可匹配）。
• 遍历结束后，open和close的总和必为偶数（因字符串长度为偶数），计算最小成本：
  • 每两个相同的未匹配括号（如{{或}}）只需1次转换；
  • 每一对不同的未匹配括号（}{）需要2次转换。
  • 最终成本公式为 (open / 2) + (close / 2) + (open % 2)（因open和close奇偶性一致，open%2等价于close%2）。

优化后的代码 #

int findMinimumCost(string str) {
    int n = str.length();
    if (n % 2 != 0) {
        return -1;
    }
    int open = 0, close = 0;
    for (char c : str) {
        if (c == '{') {
            open++;
        } else {
            if (open > 0) {
                open--;
            } else {
                close++;
            }
        }
    }
    return (open / 2) + (close / 2) + (open % 2);
}

优化效果说明 #

• 解决溢出问题：迭代遍历方式支持任意长度的输入字符串，不会触发栈溢出。
• 空间复杂度降至O(1)：仅使用两个变量计数，无需额外栈空间。
• 时间复杂度保持O(n)：仅需一次遍历即可完成计算，效率最优。

内容的提问来源于stack exchange，提问作者sreetam