在Python中找出一个列表中每个分区的大小,其中每个字母最多只出现一次的程序
假设我们有一个小写字符串s,我们可以将s分成尽可能多的部分,使得每个字母最多只出现在一部分中,并将分区的大小作为列表查找。
因此,如果输入是s =“momoplaykae”,那么输出将是[4, 1, 1, 4, 1],因为字符串被分成 [“momo”,“p”,“l”,“ ayka”,“e”]。
为了解决这个问题,我们将遵循以下步骤-
- count:包含s中字符及其出现次数的映射
-
out:一个新的列表,stk:一个空堆栈
-
长度:0
-
对于s中的每个字符,执行以下操作
- count [char]:=count [char] -1
-
长度:=长度+1
-
while count [char]与0不同或stk不为空
- 如果count [char]不同于0,则
-
将char推入stk中
-
退出循环
-
如果stk不为空且count [stk顶部]与0相同,则
-
从stk弹出
-
否则,
-
退出循环
-
如果stk为空并且count [char]与0相同,则
- 在out后插入长度
-
长度:= 0
-
返回out
更多Python相关文章,请阅读:Python 教程
示例
让我们看下面的实现,以更好地理解-
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]