文字列から重複する文字を削除するアルゴリズム

Question

文字列 "abbashbhqa"を持ってみましょう。出力が "abshq"になるように、重複する文字を削除する必要があります。考えられる解決策の1つは、各文字を文字列内の他の文字と照合して操作することです。しかし、これはO（n^2）時間の複雑さを必要とする。それを行うための最適化されたアプローチはありますか？

Answer 1

O（N）である：

はブール値のアレイL [26]を定義します。 allをFALSEに設定します。 新しい空の文字列を作成します。

文字列を移動し、L [x]がFALSEかどうかを確認します。その場合は、xを新しい文字列に追加し、L [x]を1に設定します。

新しい文字列を古い文字列にコピーします。

Answer 2

あなたが文字列を反復するとすぐにセット（またはハッシュセット）を作成します。アルファベットが制限されている場合（あなたの例のように英字）には、256のブール値配列を作成してASCIIコードをキーとして使用できます。出発点ですべてのブール値をfalseにする。 array []がfalseまたはtrueの場合にチェックする各反復。 falseの場合、シンボルは重複していないので、array [] = trueにマークし、文字列から削除してはいけません。場合それは本当 - シンボルが重複

Answer 3

は、おそらくこれは、上記の問題の実装になります

import java.util.*; 
import java.io.*; 

public class String_Duplicate_Removal 
{ 

    public static String duplicate_removal(String s) 
    { 
     if(s.length()<2) 
      return s; 

     else if(s.length()==2) 
     { 
      if(s.charAt(0)==s.charAt(1)) 
       s = Character.toString(s.charAt(0)); 
      return s; 
     } 

     boolean [] arr = new boolean[26]; 

     for(int i=0;i<s.length();i++) 
     { 

      if(arr[s.charAt(i)-'a']==false) 
       arr[s.charAt(i)-'a']=true; 

      else 
      { 
       s= ((new StringBuilder(s)).deleteCharAt(i)).toString(); 
       i--; 
      } 
     } 
     return s; 
    } 

    public static void main(String [] args) 
    { 
     String s = "abbashbhqa"; 
     System.out.println(duplicate_removal(s)); 
    } 
} 

Answer 4

私は、Pythonを使って解決していますし、それはO（n）の時間とO（n）の空間で動作します - 私はセットを使用しています（）この場合、要素の順序が変更されます。 - オーダーを同じままにしたい場合は、OrderedDict（）を使用することができ、O（n）時にも動作します。