程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式師世界 >> 編程語言 >  >> 更多編程語言 >> Python

Remove duplicate letters Python solution

編輯:Python

Give you a string  s , Please remove the duplicate letters from the string , Make each letter appear only once . To be guaranteed   The dictionary order of the returned result is the smallest ( The relative position of other characters should not be disturbed ).

example :

 Input :s = "cbacdcbc"
 Output :"acdb"

analysis :

The subject of the topic is de duplication , Then it requires that the lexicographic order of the returned results be minimized , Is to ensure that each character appears only once , Try to make the strings orderly , From small to large .

The method is to design a stack , If it is stored in the stack, skip , If not , Then judge first , Whether the top element of the stack can be taken out , If characters following string include top of stack elements , And the stack top element is larger than the current element , Then you can take out the top element of the stack , Then put the current element in , In this way, local sorting can be realized , And subsequent elements will be supplemented .、

Code :

class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
n = len(s) # String length
stack = [] # Create a stack
for i in range(n): # Traversal string
if s[i] in stack: # The current character has been stored in the stack
continue
else: # The current character has not been stored on the stack
while stack and stack[-1] > s[i] and stack[-1] in s[i + 1:]: # The stack is not empty and the top of the stack element is larger than the current element and the top of the stack element exists in subsequent elements ( Otherwise, it cannot be supplemented )
stack.pop() # Pop up top element
stack.append(s[i]) # Stack the current element
return ''.join(stack) # Connect the elements in the stack into a string 


  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式師世界 All Rights Reserved