在一次面试中提出的一个很好的后续问题是“有效括号”问题。
给定一个不平衡的括号字符串，只要完成最少数量的括号加法，就返回具有平衡括号的结果字符串（多个解决方案中的任意一个）。
例如。
- “(){([)}()” -> “(){([])}()”
- “([)]” -> “([()])” 或 “()[()]” 或 “[([])]”
很容易得到平衡字符串所需的最小加法次数，但精确的字符串却很棘手，无法通过最小加法得到最佳解决方案。我倾向于使用递归/动态规划解决方案来评估形成的最小长度平衡子字符串的每一个选择。
欢迎任何建议/方法
10
最佳答案
1
我们text将输入括号字符串定义为：
sol(x, y) = min_addition_count to handle text[x:y]
并且 sol(x, y) 是这两种情况中的最小值：
1. sol(x + 1, y - 1) if text[x] and text[y] is match(eg. text[x] is '(' and text[y] is ')')
2. sol(x, i) + sol(i + 1, y) for i >= x and i < y
对于特殊情况，我们有：
sol(x, y) = 1 for x == y
sol(x, y) = 0 for x > y
在解答的过程中，我们记录下我们的解（最小加法账户）是从哪里来的，得到解之后就可以去寻找答案了。
你可以查看我的 Python 代码来了解详细信息：
def find_solution(text):
mem = {}
# mem[x, y] is a tuple (α, β), where α is the minimum addition count, and β is where α comes from.
# so β can be 2 cases: [(x + 1, y - 1)] or [(x, x + i), (i + 1, y)]
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), []
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]: # case1
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]: # case2
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('()[()}'))
print(find_solution('({)[]'))
输出：
(){([])}()
()()()
([])[]
()()
()[](){}
({})[]
如果您有任何疑问，请随时在此发表评论。
6
-
什么
sol(i + 1, x) for i >= x意思？ 的第一个参数怎么能sol大于它的第二个参数呢？
–
-
@Sayakiss 上面的代码我突然想不起来，你能在主要步骤中添加一些注释吗？我是 Python 新手。
– -
@גלעדברקן 这是一个错误，应该是
sol(x, i) + sol(i + 1, y)。我修改了我的答案。
– -
@Shailendra 我认为这是因为您不熟悉通过记忆进行动态规划。您可以查看这篇文章以了解如何处理更简单的任务：
– -
@Shailendra 我添加了一些评论来帮助你跟上。最好先阅读那篇文章。
–
|
[([])]第二个例子吗？–
–
[([])]也是解决方案之一，您只需给出 1 个答案，可以是任何结果。我没有包括它，因为在我的脑海中，我一直遵循贪婪直到不平衡点，然后尝试使用递归来平衡此时的 2 个选择。–
–
O(n)级别效率低下的问题，那就更难了。）–
|