21. Remove Duplicate Letters

10826 ワード
アルゴリズム#アルゴリズム# テキストリンク
道しるべ
  • の重複文字を除き、
    • がアルファベット順(Lexicographical Order)にリストされます.

    1.再帰的分離利用（52 ms）

    
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        #집합으로 정렬
        
        for char in sorted(set(s)):
            suffix = s[s.index(char):]
            
            #전체 집합과 접미사 집합이 일치할 때 분리 진행
            
            if set(s) == set(suffix):
                return char + self.removeDuplicateLetters(suffix.replace(char,''))
            
        return ''

  • ディクショナリ順序
    :文字通り、辞書で最初に見つけた順番

  • bcabcの重複文字を除いて、辞書で最初に見つけられる文字列はabcになります.

  • 前にe文字を追加したebcabcが入力値である場合、結果はeabcになります.

  • e文字自体はこの文字列内でアルファベット順に最後に並べられているが、eは入力値に一度しか現れず、a、b、cはその後現れるため、eの位置を変更することはできない.

  • 逆に、入力値がebcabceである場合、最初のeは繰り返し削除され、最後のeはabceとして保持され得る.

  • すべての文字列入力値を重複文字以外の(ここでは集合)のアルファベット順に並べ替え、最速のaから接尾辞を分離して確認します.

  • 次の順序はbであり,bに対してc,dが上位にランクインできないため,これを標準として分離することはできない.

  • 分離可能か否かは、本コードに示すように、集合全体が接尾辞集合と一致するか否かによって判別される.
  • 集合は重複文字を消去するデータ型であるため、bを基準とした場合、s={'b'、'c'、'd'}、接尾辞={'b'、'c'}となり、dを別々に処理することはできない.従って、次の順序cに移る.
  • 現在、cはs={'b','c','d'}、接尾辞={'b','c','d'}であり、一致するか否かを判別するためのif文はTrueであるため、分離することができる.

  • ここから実際の処理分離を開始し,現在の文字,すなわちcの再帰呼び出し構造を返す.
  • また、cは分離の基準点となり、次のすべてのcはreplace()で除去される.
  • は、分割征服の形式に似ており、接尾辞の大きさはますます小さくなり、残りがなくなった場合、遡及するにつれて結果は組み合わされる.
    • ＜回帰分離利用＞
  • cbacdcbcを辞書順に重複文字を除去するプロセスのアルゴリズムは、次のようになり、結果として青色文字のacdbになります.

    • 2.スタックを使用して文字を削除(32ミリ秒)

    
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        counter, seen, stack = collections.Counter(s), set(), []
        
        for char in s:
            counter[char] -= 1
            if char in seen:
                continue
                
            #뒤에 붙일 문자가 남아 있다면 스택에서 제거
            while stack and char < stack[-1] and counter[stack[-1]] > 0:
                seen.remove(stack.pop())
            
            stack.append(char)
            seen.add(char)
            
        return ''.join(stack)

  • まず、スタックは前から順番に積み上げます

  • 現在の文字がスタックに積み重ねられた文字(前の文字よりも早い)であり、後に貼り付けられる文字(カウンタが0より大きい)がある場合は、積み重ねられた文字を取り出して破棄します.

  • カウントにはcollectionsが含まれています.カウンタ()を使用します.
  • このモジュールは、各文字の数を自動的に計算するので、他の章でも様々な問題に使用できます.

  • seedは、処理された文字がスキップされるかどうかを決定する集合データ型(set)である.

  • 処理後の文字が正しいかどうかを確認するためにinで検索演算を行った.

  • この機能はスタックに存在しない演算であるため、個別の集合データ型にのみ使用されます.

  • リストは検索をうまくサポートしているので,スタックの資料構造に限定されずに解くと,可視変数がなくても以下のような形で解くことができる.
    •   	
    def removeDuplicateLetters(self, s:str) -> str:
        counter, stack = collections.Counter(s), []
        
        for char in s:
            counter[char] -= 1
            if char in stack:
                continue
                
            # 뒤에 붙일 문자가 남아 있다면 스택에서 제거
            
            while stack and char < stack[-1] and counter[stack[-1]] > 0:
                stack.pop()
                
             stack.append(char)
             
       return ''.join(stack)
  • しかし、スタック内にない探索演算を実行するための変分解方法であるため、ここでは、スタック内でのみ可能な演算を実行するのが慣例であり、探索機能は、以下に示すように、所見の変数で実行される.
    • <スタック文字プールの削除>

  • cbacdbaからaが入力されると、以下に示すように、入力されたcおよびbは削除されます.
  • カウンタが0以上の文字cとbの後ろには貼り直す文字があるからです.
    • 🐧Linuxクラスタ
    Shadow DOMを使ってProgress barを飾ります!