leetcode
leetcode 1151 ~ 1200
移除无效的括号

移除无效的括号

难度:

标签:

题目描述

代码结果

运行时间: 50 ms, 内存: 17.5 MB


/*
 * 思路:
 * 使用Java Stream API来简化代码:
 * 1. 使用过滤器去掉多余的右括号 ')'
 * 2. 使用过滤器去掉多余的左括号 '('。
 */

import java.util.stream.Collectors;

public class Solution {
    public String minRemoveToMakeValid(String s) {
        int open = 0;
        StringBuilder sb = new StringBuilder();
        // First pass: remove extra ')'
        s.chars().forEach(c -> {
            if (c == '(') open++;
            if (c == ')') {
                if (open == 0) return;
                open--;
            }
            sb.append((char) c);
        });
        open = 0;
        String result = sb.reverse().chars()
            .filter(c -> {
                if (c == ')') open++;
                if (c == '(') {
                    if (open == 0) return false;
                    open--;
                }
                return true;
            })
            .mapToObj(c -> String.valueOf((char) c))
            .collect(Collectors.joining());
        return new StringBuilder(result).reverse().toString();
    }
}

解释

方法:

此题解通过利用栈结构来跟踪并处理字符串中的括号。首先,将字符串转换为字符数组,以便能够修改特定索引的字符。遍历字符数组时,遇到'('时将其索引入栈,表示一个潜在的未匹配左括号。遇到')'时,检查栈是否为空:如果不为空,表示栈顶的'('可以与之匹配,于是将其出栈;如果为空,说明当前的')'无法匹配,将其位置上的字符设为空字符串。遍历完成后,栈中剩余的都是未能匹配的'('的索引,将这些位置上的字符同样设为空字符串。最后,将修改后的字符数组重新组合成字符串。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在处理无法匹配的')'时,直接将其设为空字符串,这是否意味着这个字符会在最终的字符串中完全消失?
是的,当代码遇到无法匹配的')'时,将其设为空字符串确实意味着这个字符在最终的字符串中会完全消失。这是因为将字符设为空字符串相当于在数组中删除该字符,而最后使用''.join(s)时,这些空字符串将不会被包括在内,从而在结果字符串中不再出现这些无效的括号。
🦆
如何确定所有未匹配的'('在栈中的索引,并确保它们在最后被正确地删除?
算法中使用一个栈来存储每个'('字符的索引。当遇到一个')'字符时,如果栈不为空,则从栈中弹出一个元素,这表示找到了一个匹配的括号对。如果遍历结束后栈仍有元素,这些元素即为未匹配的'('的索引。通过遍历栈并将这些索引对应的字符在字符数组中设为空字符串,这样可以确保这些未匹配的'('在最终字符串中被删除。
🦆
此算法是否考虑了输入字符串中只含有小写字母而没有任何括号的情况?如果是,算法是如何处理这种情况的?
是的,此算法也考虑了输入字符串中只含有小写字母而不含任何括号的情况。在这种情况下,由于字符串中不存在括号,栈操作(入栈和出栈)将不会发生,字符数组也不会进行任何修改。因此,最终通过''.join(s)返回的结果将是原始输入字符串本身,未发生任何改变。

相关问题