Python 中不同字符的最小子序列
pythonserver side programmingprogramming更新于 2025/8/25 7:08:17
假设我们有一个文本,我们必须找到按字典顺序排列的最小文本子序列,该子序列包含文本的所有不同字符,且恰好一次。因此,如果输入为"cdadabcc",则输出为"adbc"。
为了解决这个问题,我们将遵循以下步骤 −
- 定义一个堆栈 st、两个映射 last_o 和 considered,它们最初是空白的
- for i in range length of text – 1 down to 0
- if text[i] is not present in last_o −
- last_o[text[i]] := i
- considered[text[i]] := false
- i := 0
- 当 i < 文本长度
- 如果堆栈没有元素
- 将 text[i] 推入堆栈
- considered[text[i]] := true
- 将 i 增加 1
- 否则堆栈顶部 > text[i] 且 considered[text[i]] 为 false
- 如果 last_o[stack top] > i
- considered[stack top element] := false
- 从堆栈弹出
- 否则
- considered[tex[i]] = true
- 将 text[i] 插入堆栈
- 将 i 增加 1
- 如果 last_o[stack top] > i
- 否则,当堆栈顶部元素 < temp[i] 且 considered[text[i]] = false
- 将 text[i] 插入堆栈
- considered[text[i]] := true
- 将 i 增加 1
- 否则将 i 增加 1
- 如果堆栈没有元素
- if text[i] is not present in last_o −
- 以相反的顺序返回堆栈的所有元素作为字符串
让我们看看下面的实现以便更好地理解 −
示例
class Solution(object):
def smallestSubsequence(self, text):
"""
:type text: str
:rtype: str
"""
stack = []
last_o = {}
considered = {}
for i in range(len(text)-1,-1,-1):
if text[i] not in last_o:
last_o[text[i]] = i
considered[text[i]] = False
print(last_o)
i = 0
while i < len(text):
print(stack,i,text[i])
if len(stack) == 0:
stack.append(text[i])
considered[text[i]] = True
i+=1
elif stack[-1]>text[i] and considered[text[i]] == False:
if last_o[stack[-1]]>i:
considered[stack[-1]]=False
stack.pop()
else:
considered[text[i]] = True
stack.append(text[i])
i+=1
elif stack[-1]<text[i] and considered[text[i]] == False:
stack.append(text[i])
considered[text[i]] = True
i+=1
else:
i+=1
return "".join(i for i in stack)
输入
"cdadabcc"
输出
"adbc"
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

