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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习