找到平衡括号的最小编辑数量？

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: (()(()()))()((()))