Pythonの個別の文字の最小のサブシーケンス

テキストがあるとすると、テキストのすべての異なる文字を1回だけ含む、辞書式順序で最小のテキストのサブシーケンスを見つける必要があります。したがって、入力が「cdadabcc」のような場合、出力は「adbc」になります。

これを解決するには、次の手順に従います-

• スタックst、2つのマップlast_oを定義し、考慮します。最初は空白です
• テキストの範囲の長さのiの場合–1から0まで
  • text[i]がlast_oに存在しない場合-
    • last_o [text [i]]：=i
    • 考察[text[i]]：=false
  • i：=0
  • whilei<テキストの長さ
    • スタックに要素がない場合
      • text[i]をスタックにプッシュ
      • 考察[text[i]]：=true
      • iを1増やします
    • それ以外の場合、スタックトップ>text[i]および考慮される[text[i]]はfalse
      • if last_o [stack top]> i
        • 考慮[スタックトップ要素]：=false
        • スタックからポップ
      • それ以外の場合
        • considered [tex [i]] =true
        • テキスト[i]をスタックに挿入
        • iを1増やします
    • それ以外の場合、スタックトップ要素
    • テキスト[i]をスタックに挿入
    • 考察[text[i]]：=true
    • iを1増やします
  • それ以外の場合は、iを1増やします

理解を深めるために、次の実装を見てみましょう-

例

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"