给出结果字符串，为使字符串平衡而添加括号的最少次数

Question

在采访帖子“有效括号”问题之一中提出了一个很好的后续问题。

给定一个不平衡的括号字符串，返回具有平衡括号的结果字符串（多个解决方案中的任何一个），前提是完成了最少数量的括号加法。
例如。

• “(){([)}()”->“(){([])}()”
• “([)]”->“([()])”或“()[()]”或“[([])]”

很容易获得平衡字符串所需的最小加法的计数，但精确的字符串很棘手，无法得出采用最小加法获得字符串的最佳解决方案。 我倾向于使用递归/动态编程解决方案来评估形成的最小长度平衡子串的每个选择。

欢迎任何建议/方法

Answer 1

我们定义

text

是输入括号字符串并且：

sol(x, y) = min_addition_count to handle text[x:y]

并且 sol(x, y) 是这些情况的最小值：

sol(x + 1, y - 1) if text[x] and text[y] is match(eg. text[x] is '(' and text[y] is ')')
sol(x, i) + sol(i + 1, x) for i >= x and i < y

对于极端情况

x == y

，我们有：

sol(x, x) = 1

在求解过程中，我们记录我们的解（最小加法账户）从哪里来，然后我们得到解后就可以找到解了。

详细内容可以查看我的Python代码：

def find_solution(text):
    mem = {}

    def sol(x, y):
        if mem.get((x, y)) is not None:
            return mem[x, y]
        if x > y:
            mem[x, y] = 0, None
            return mem[x, y]
        if x == y:
            mem[x, y] = 1, None
            return mem[x, y]
        ans = len(text), '', True
        if (text[x] == '(' and text[y] == ')') or (text[x] == '[' and text[y] == ']') or (
                text[x] == '{' and text[y] == '}'):
            if ans[0] >= sol(x + 1, y - 1)[0]:
                ans = sol(x + 1, y - 1)[0], [(x + 1, y - 1)]
                mem[x, y] = ans
        for i in range(x, y):
            if ans[0] >= sol(x, i)[0] + sol(i + 1, y)[0]:
                ans = sol(x, i)[0] + sol(i + 1, y)[0], [(x, i), (i + 1, y)]
                mem[x, y] = ans
        return mem[x, y]

    def get_solution(x, y):
        if x > y:
            return ''
        if x == y:
            t = text[x]
            if t == '(' or t == ')':
                return '()'
            if t == '[' or t == ']':
                return '[]'
            if t == '{' or t == '}':
                return '{}'
        sol = mem[x, y]
        if len(sol[1]) == 1:
            return text[x] + get_solution(*sol[1][0]) + text[y]
        if len(sol[1]) == 2:
            return get_solution(*sol[1][0]) + get_solution(*sol[1][1])

    sol(0, len(text) - 1)
    return get_solution(0, len(text) - 1)


print(find_solution('(){([)}()'))
print(find_solution(')))'))
print(find_solution('([)]'))
print(find_solution('()()'))
print(find_solution('()[()}'))

输出：

(){([])}()
()()()
([])[]
()()
()[](){}

如果您有任何疑问，请随时在这里发表评论。