1249. 移除无效的括号

以下是对这段 Python 代码的详细讲解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def minRemoveToMakeValid(self, s: str) -> str:
    # Parse 1: Remove all invalid ")"
    first_parse_chars = []
    balance = 0
    open_seen = 0
    for c in s:
        if c == "(":
            balance += 1
            open_seen += 1
        if c == ")":
            if balance == 0:
                continue
            balance -= 1
        first_parse_chars.append(c)
  • 这段代码定义了一个名为 minRemoveToMakeValid 的方法，它接受一个字符串 s 作为输入，并返回一个修改后的字符串。
  • 首先，创建了一个空列表 first_parse_chars 用于存储第一次处理后的字符。
  • 初始化两个变量 balance 和 open_seen，balance 用于跟踪左右括号的平衡状态，open_seen 用于统计出现的左括号数量。
  • 遍历输入字符串 s 中的每个字符 c：
    • 当字符 c 是 ( 时，将 balance 和 open_seen 的值都加 1。这表示我们看到了一个左括号，并且增加了左括号的计数。
    • 当字符 c 是 ) 时：
      • 检查 balance 的值，如果 balance 为 0，说明此时的 ) 是多余的，因为没有对应的左括号与之匹配，因此使用 continue 语句跳过将该 ) 加入 first_parse_chars 列表。
      • 如果 balance 不为 0，则将 balance 的值减 1，表示找到了一个匹配的左括号，将这个 ) 加入 first_parse_chars 列表。
1
2
3
4
5
6
7
8
9
# Parse 2: Remove the rightmost "("
result = []
open_to_keep = open_seen - balance
for c in first_parse_chars:
    if c == "(":
        open_to_keep -= 1
        if open_to_keep < 0:
            continue
    result.append(c)
  • 在第二次解析中，我们要移除多余的左括号。
  • 创建一个新的空列表 result 来存储最终的结果。
  • 计算 open_to_keep 的值，它等于 open_seen 减去 balance。这个值表示最终应该保留的左括号数量。
  • 再次遍历 first_parse_chars 列表中的每个字符 c：
    • 当字符 c 是 ( 时，将 open_to_keep 的值减 1。
    • 如果 open_to_keep 的值小于 0，说明这个左括号是多余的，使用 continue 跳过添加该字符到 result 列表。
    • 否则，将该字符添加到 result 列表中。
1
return "".join(result)
  • 最后，使用 join 方法将 result 列表中的字符拼接成一个字符串并返回。

代码逻辑总结：

  • 这段代码的主要目的是从输入字符串中移除最少的括号，使得剩余的括号是平衡的。
  • 在第一次解析中，它移除了所有多余的右括号。通过 balance 变量，如果在遇到右括号时 balance 为 0，则说明该右括号是多余的，不添加到 first_parse_chars 列表。
  • 在第二次解析中，根据第一次解析后的结果，计算应该保留的左括号数量 open_to_keep，并移除多余的左括号。
  • 最终返回一个括号平衡的字符串。

示例：

  • 假设输入字符串 s 为 ()())()。
  • 在第一次解析中：
    • 当遍历到第一个 ( 时，balance 变为 1，open_seen 变为 1，添加 ( 到 first_parse_chars。
    • 遇到第一个 ) 时，balance 变为 0，添加 ) 到 first_parse_chars。
    • 遇到第二个 ) 时，balance 为 0，跳过该 )。
    • 遇到第三个 ) 时，balance 为 0，跳过该 )。
    • 遇到第二个 ( 时，balance 变为 1，open_seen 变为 2，添加 ( 到 first_parse_chars。
    • 遇到最后一个 ) 时，balance 变为 0，添加 ) 到 first_parse_chars。
    • 此时 first_parse_chars 为 ()()()。
  • 在第二次解析中：
    • open_to_keep 为 open_seen - balance 即 2 - 0 = 2。
    • 当遇到第一个 ( 时，open_to_keep 变为 1。
    • 当遇到第二个 ( 时，open_to_keep 变为 0。
    • 最终结果 result 为 ()()()。

该代码通过两次解析和使用两个变量 balance 和 open_to_keep 有效地实现了从字符串中移除最少的括号以保证括号平衡的功能。