ARTS #66 | pdb

Algorithm

规则如下：

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

Solution

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        # 找出不匹配的括号类型和数量
        left, right = 0, 0
        for char in s:
            if char == '(':
                left += 1
            elif char == ')':
                if left == 0: right += 1
                if left > 0: left -= 1
        
        # 找出所有可能的结果
        result = set()
        def match(rem_left: int, rem_right: int, index:int, curr_str: str):
            if index == len(s):
                if rem_left + rem_right == 0:
                    result.add(curr_str)
                return
            if rem_left + rem_right == 0:
                result.add(curr_str + s[index:])
                return

            char = s[index]
            if char == "(" and rem_left > 0:
                match(rem_left - 1, rem_right, index + 1, curr_str)
            elif s[index] == ")" and rem_right > 0:
                match(rem_left, rem_right - 1, index + 1, curr_str)
            match(rem_left, rem_right, index + 1, curr_str + char)
        match(left, right, 0, "")

        # 对结果进行筛选
        def is_valid(s: str) -> bool:
            stack = []
            for c in s:
                if c == "(":
                    stack.append(c)
                elif c == ")":
                    if not stack or stack.pop() != "(":
                        return False
            return len(stack) == 0
        return list(filter(is_valid, result))

主要就是分为三步：

找出不匹配的括号类型和数量 - 作为 Base Case，后面穷举时可以提前结束查找过程
找出所有可能的结果 - 穷举
对结果进行筛选 - 判断是否是有效的括号对

耗时460ms，显然还存在优化空间。

尝试了用数组代替字符串的频繁修改，不过优化程度有限；从评论区得到 left_count、right_count 灵感，结合数组的优化后最终代码如下：

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        # 找出不匹配的括号类型和数量
        left, right = 0, 0
        for char in s:
            if char == '(':
                left += 1
            elif char == ')':
                if left == 0: right += 1
                if left > 0: left -= 1
        
        # 找出所有有效的结果
        result = set()
        def match(rem_left: int, rem_right: int, index:int, left_count: int, right_count: int, curr_str: []):
            if index == len(s):
                if rem_left + rem_right == 0:
                    result.add("".join(curr_str))
                return

            char = s[index]
            if char == "(" and rem_left > 0:
                match(rem_left - 1, rem_right, index + 1, left_count, right_count, curr_str)
            elif s[index] == ")" and rem_right > 0:
                match(rem_left, rem_right - 1, index + 1, left_count, right_count, curr_str)
            
            curr_str.append(char)
            if char != "(" and char != ")":
                match(rem_left, rem_right, index + 1, left_count, right_count, curr_str)
            elif char == "(":
                match(rem_left, rem_right, index + 1, left_count + 1, right_count, curr_str)
            elif char == ")" and left_count > right_count:
                match(rem_left, rem_right, index + 1, left_count, right_count + 1, curr_str)
            curr_str.pop()
        match(left, right, 0, 0, 0, [])
        return list(result)

Review

Six Debugging Techniques for Python Programmers

这篇文章列举了6种调试手段：

Print and Check
Assert and Check
Using Logging Module
pdb
IDE
Pen and Paper :)

几乎所有的方法我都用过 - 除了 pdb。

看起来 pdb 支持的指令很全，而且使用方法相当简单，大多数语义和 lldb 类似，使用门槛很低。

不过文章中出现了一处小错误:

Python gives us more flexibility when using assert. We can use the -0 parameter to close all the assert statements in the program when starting the Python interpreter. After that, all the assert methods will not work.
python -0 assert.py
# Traceback (most recent call last):
#   ...
# ValueError: invalid literal for int() with base 10: 'Yang'

移除断言语句的命令行参数是-O(大写字母O)而不是-0(数字)。

Tip

禁用断言：

python3 -O /path/to/file

以 pdb 调试模式执行：

python3 -m pdb /path/to/file

在代码中通过函数插入 pdb 断点：

breakpoint()

完整的 pdb 指令清单：传送门

关于 Swift 枚举本质的思维导图：

xmind

Algorithm

Solution

Review

Tip

Share