Python程序：移除相邻不同位后找到最短字符串

假设我们有一个二进制字符串s，如果两个相邻字符不同，我们可以删除它们。最终，我们需要找到如果可以执行此操作任意多次，我们可以获得的最短字符串的长度。

因此，如果输入类似于s = "1100011"，则输出将为1，因为删除“10”后得到“10011”，然后再次删除“10”，它将变为“011”，然后删除“01”，剩下1。

为了解决这个问题，我们将遵循以下步骤：

• stack := 新建一个列表
• 对于s中的每个字符c，执行以下操作：
  • 如果stack为空或stack的顶部与c相同，则
    • 将c压入stack
  • 否则，如果stack的顶部与c不同，则
    • 从stack中弹出元素
• 返回stack中元素的个数

让我们看看下面的实现来更好地理解：

示例

 在线演示

class Solution:
   def solve(self, s):
      stack = []
      for c in s:
         if not stack or stack[-1] == c:
            stack.append(c)
         elif stack[-1] != c:
            stack.pop()
      return len(stack)
ob = Solution() print(ob.solve("1100011"))

输入

"1100011"

输出

1

Arnab Chakraborty

更新于：2020年10月5日

239 次浏览

开始你的职业生涯

完成课程获得认证

开始学习