Chương trình tìm một chuỗi tốt từ một chuỗi đã cho bằng Python

Giả sử chúng ta có một chuỗi s với các chữ cái tiếng Anh viết thường và viết hoa. Chúng tôi sẽ coi một chuỗi là một chuỗi tốt không có bất kỳ hai ký tự liền kề nào s [i] và s [i + 1] trong đó -

• 0 <=i <=size of s - 2

• s [i] là chữ thường và s [i + 1] là cùng một chữ cái nhưng viết hoa hoặc ngược lại.

Để chuyển một chuỗi thành chuỗi tốt, chúng ta có thể chọn hai ký tự liền kề khiến chuỗi xấu và loại bỏ chúng. Chúng tôi sẽ tiếp tục quá trình này cho đến khi chuỗi trở nên tốt, (Một chuỗi rỗng có thể là một chuỗi tốt). Chúng tôi phải tìm chuỗi sau khi làm cho nó tốt.

Vì vậy, nếu đầu vào là s =​​"popPpulaBbr", thì đầu ra sẽ là "phổ biến", vì lúc đầu hoặc xóa "p ^P "hoặc" P _p "và xóa" Bb ".

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

• res:=một danh sách mới

• đối với mỗi ký tự ch trong s, thực hiện

  • nếu res không trống và phần tử cuối cùng trong res giống với ch trong mọi trường hợp viết hoa hoặc viết thường, thì

    • xóa phần tử cuối cùng khỏi res

  • nếu không,

    • chèn ch vào cuối res

• nối từng phần tử có trong res và trả về nó

Ví dụ (Python)

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

def solve(s):
   res = []
   for ch in s:
      if res and res[-1] != ch and res[-1].lower() == ch.lower():
         res.pop()
      else:
         res.append(ch)
   return ''.join(res)

s = "popPpulaBbr"
print(solve(s))

Đầu vào

"popPpulaBbr"

Đầu ra

popular