Python에서 연속적인 중복 문자를 제거한 후 문자열을 찾는 프로그램

문자열 s가 있다고 가정하고 첫 번째 연속 중복 문자를 반복적으로 삭제합니다. 마지막 문자열을 찾아야 합니다.

따라서 입력이 s ="xyyyxxz"와 같으면 "yyy"가 삭제될 첫 번째 연속 중복 문자이므로 출력은 "z"가 됩니다. 그래서 우리는 "xxxz"가 있습니다. 그런 다음 "xxx"가 삭제되어 "z"로 끝납니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 스택 :=새 스택
• i :=0
• i
• 스택이 비어 있지 않고 스택의 맨 위가 s[i]와 같으면
  • x :=스택에서 마지막 요소 삭제
  • i
  • 나는 :=나는 + 1
• 나는 :=나는 - 1

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, s):
      stack = []
      i = 0
      while i < len(s):
         if len(stack) and stack[-1] == s[i]:
            x = stack.pop()
            while i < len(s) and x == s[i]:
               i += 1
            i -= 1
            else:
               stack.append(s[i])
            i += 1
      return "".join(stack)
ob = Solution()
s = "xyyyxxz"
print(ob.solve(s))

입력

"xyyyxxz"

출력

z