Python 中移除字串中所有相鄰重複字元

假設我們有一個由小寫字母組成的字串 S；將執行重複字元移除操作。這將透過選擇兩個相鄰且相等的字母並將其移除來完成。

我們將重複從 S 中移除重複字元，直到沒有剩餘的重複字元。

在所有此類重複字元移除完成後返回字串。保證答案是唯一的。

假設字串是“abbacaca”，則答案將是“caca”。首先刪除重複字元 bb，然後字串變為“aacaca”，然後移除 aa，然後字串變為“caca”，然後沒有這樣的重複字元了。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個數組 st，並初始化 i := 0
  • 當 i < 字串長度時：
    • 如果 st 包含一些元素，並且 st 的最後一個元素 = st[i]，則將 i 加 1，並從 st 中刪除最後一個元素
    • 否則將 string[i] 新增到 st 中，將 i 加 1
  • 最後將 st 中的所有元素連線成一個字串並返回

示例

讓我們看看下面的實現以獲得更好的理解：

 線上演示

class Solution(object):
   def removeDuplicates(self, S):
      st = []
      i = 0
      while i < len(S):
         if len(st)!=0 and st[-1]==S[i]:
            i+=1
            st.pop(-1)
         else:
            st.append(S[i])
            i+=1
      return "".join(i for i in st)
ob1 = Solution()
print(ob1.removeDuplicates("abbacaca"))

輸入

"abbacaca"

輸出

"caca"

更新於: 2020-04-28

3K+ 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告