Chương trình tìm chuỗi ngắn nhất sau khi loại bỏ các bit liền kề khác nhau trong Python

Giả sử chúng ta có một chuỗi nhị phân s, chúng ta có thể xóa hai ký tự liền kề bất kỳ nếu chúng khác nhau. Cuối cùng, chúng ta phải tìm độ dài của chuỗi nhỏ nhất mà chúng ta có thể nhận được nếu chúng ta có thể thực hiện thao tác này nhiều lần tùy ý.

Vì vậy, nếu đầu vào là s =​​"1100011", thì đầu ra sẽ là 1, như Sau khi xóa "10" chúng ta nhận được "10011", sau đó lại xóa "10", nó sẽ là "011", sau đó xóa "01 ", nó sẽ còn lại 1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• stack:=một danh sách mới
• đối với mỗi c trong s, thực hiện
  • nếu ngăn xếp trống hoặc đầu ngăn xếp giống với c, thì
    • đẩy c vào ngăn xếp
  • ngược lại khi đầu ngăn xếp không giống với c, thì
    • phần tử pop từ ngăn xếp
• trả về số phần tử trong ngăn xếp

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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"))

Đầu vào

"1100011"

Đầu ra

1