Python程式：查詢列表中每個分割槽的長度，其中每個字母最多出現在一個分割槽中

Python 伺服器端程式設計程式設計

假設我們有一個小寫字串s，我們可以將s儘可能多地劃分成多個部分，使得每個字母最多出現在一個部分中，並找到這些分割槽的大小，將其作為一個列表。

因此，如果輸入類似於s = "momoplaykae"，則輸出將為[4, 1, 1, 4, 1]，因為字串被分成["momo", "p", "l", "ayka", "e"]。

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

count := 一個包含s中字元及其出現次數的對映
out := 一個新的列表，stk := 一個空的棧
length := 0
對於s中的每個字元，執行：
- count[char] := count[char] - 1
- length := length + 1
- 當count[char]不等於0或stk不為空時，執行：
  - 如果count[char]不等於0，則
    - 將char壓入stk
    - 退出迴圈
  - 如果stk不為空且count[stk的頂部元素]等於0，則
    - 從stk中彈出元素
  - 否則，
    - 退出迴圈
- 如果stk為空且count[char]等於0，則
  - 在out之後插入length
  - length := 0
返回out

示例

讓我們看看下面的實現，以便更好地理解：

線上演示

from collections import Counter
class Solution:
   def solve(self, s):
      count = Counter(s)
      out = []
      stk = []
      length = 0
      for char in s:
         count[char] -= 1
         length += 1
         while count[char] != 0 or stk:
            if count[char] != 0:
               stk.append(char)
               break
            if stk and count[stk[-1]] == 0:
               stk.pop()
            else:
               break
            if not stk and count[char] == 0:
               out += [length]
               length = 0
         return out
ob = Solution()
s = "momoplaykae"
print(ob.solve(s))

輸入

"momoplaykae"

輸出

[4, 1, 1, 4, 1]

Arnab Chakraborty

更新於：2020年12月22日

153 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習