algorithm - 找到平衡括号的最少编辑次数？

Question

我对这个问题很困惑。我知道使用递归和动态编程作为改进来查找 2 个字符串之间的编辑距离，但是我对如何使用这个感到困惑。

不知道我的想法是否正确。但是我们有一串不平衡的括号

String s = "((())))";

如何找到需要最少编辑次数的带平衡括号的字符串？

谁能举个例子解释一下？

我仍然不确定我的解释是否正确。

Answer 1

给定一个由左右括号组成的字符串，要求我们通过执行最少数量的删除、插入和替换操作来平衡它。

首先，让我们看一下输入字符串并区分匹配对和不匹配字符。我们可以通过执行以下算法来标记属于匹配对的所有字符:

1. 找到一个未标记的“(”，后面跟着一个未标记的“)”，两者之间有零个或多个标记字符。
2. 如果不存在这样的一对字符，则终止算法。
3. 否则，标记“(”和“)”。
4. 回到第 1 步。

标记的货币对已经以零成本平衡，因此最佳做法是不再对它们进行任何操作。

现在让我们考虑未标记的字符。请注意，没有未标记的“(”后跟未标记的“)”，否则该对将被标记。因此，如果我们从左到右扫描未标记的字符，我们会发现零个或多个 ')' 字符后跟零个或多个 '(' 字符。

为了平衡 ')' 字符的顺序，最好每隔一个重写为 '('，从第一个开始，不包括最后一个。如果 ')' 字符的个数为奇数，则最好删除最后一个。

至于'('字符的顺序，最好每隔一个重写为')'，从第二个开始。如果有剩余的 '(' 字符，我们将其删除。以下 Python 代码实现上述步骤并显示中间结果。

def balance(s):  # s is a string of '(' and ')' characters in any order
  n = len(s)
  print('original string: %s' % s)

  # Mark all matched pairs
  marked = n * [ False ]
  left_parentheses = []
  for i, ch in enumerate(s):
    if ch == '(':
      left_parentheses.append(i)
    else:
      if len(left_parentheses) != 0:
        marked[i] = True
        marked[left_parentheses.pop()] = True

  # Display the matched pairs and unmatched characters.
  matched, remaining = [], []
  for i, ch in enumerate(s):
    if marked[i]:
      matched.append(ch)
      remaining.append(' ')
    else:
      matched.append(' ')
      remaining.append(ch)
  print('  matched pairs: %s' % ''.join(matched))
  print('      unmatched: %s' % ''.join(remaining))

  cost = 0
  deleted = n * [ False ]
  new_chars = list(s)

  # Balance the unmatched ')' characters.
  right_count, last_right = 0, -1
  for i, ch in enumerate(s):
    if not marked[i] and ch == ')':
      right_count += 1
      if right_count % 2 == 1:
        new_chars[i] = '('
        cost += 1
        last_right = i
  if right_count % 2 == 1:      # Delete the last ')' if we couldn't match it.
    deleted[last_right] = True  # The cost was incremented during replacement.

  # Balance the unmatched '(' characters.
  left_count, last_left = 0, -1
  for i, ch in enumerate(s):
    if not marked[i] and ch == '(':
      left_count += 1
      if left_count % 2 == 0:
        new_chars[i] = ')'
        cost += 1
      else:
        last_left = i
  if left_count % 2 == 1:      # Delete the last '(' if we couldn't match it.
    deleted[last_left] = True  # This character wasn't replaced, so we must
    cost += 1                  # increment the cost now.

  # Display the outcome of replacing and deleting.
  balanced = []
  for i, ch in enumerate(new_chars):
    if marked[i] or deleted[i]:
      balanced.append(' ')
    else:
      balanced.append(ch)
  print('        balance: %s' % ''.join(balanced))

  # Display the cost of balancing and the overall balanced string.
  print('           cost: %d' % cost)
  result = []
  for i, ch in enumerate(new_chars):
    if not deleted[i]:  # Skip deleted characters.
      result.append(ch)
  print('     new string: %s' % ''.join(result))


balance(')()(()())))()((())((')

对于测试用例')()(()())))((())(('，输出如下。

original string: )()(()())))()((())((
  matched pairs:  ()(()())  () (())
      unmatched: )        ))  (    ((
        balance: (        )   (    )
           cost: 4
     new string: (()(()()))()((()))