最初の文字列にある2番目の文字列の文字を削除します。

Question

最初の文字列にある2番目の文字列から文字を削除するプログラムを作成しました。複雑さはBigO（n^2）になります。複雑さをさらに減らすことはできますか？

public class Tmp { 

    public static void main(String[] args) { 
     String s = "halloween"; 
     String s1 = "halcyon"; 
     char[] ss = s.toCharArray(); 
     char[] ss1 = s1.toCharArray(); 

     for(int i=0;i<ss.length;i++){ 
      for(int j=0;j<ss1.length;j++){ 
       if(ss1[j] == ss[i]){ 
        ss1[j] = 'x'; //Replace the common char with x 
       } 
      } 
     } 
     System.out.println(Arrays.toString(ss1)); 
    } 
} 

OUTPUT

[x, x, x, c, y, x, x] 

Answer 1

1. 最初の文字列をマップに変換します。他の文字列上のO（N）
2. 反復ステップ1 O（N）からマップに存在文字+ O（1）

合計時間複雑度= O（N）

かどうかを確認ここでは、MAPを格納するためのスペースがさらに複雑になります。

Answer 2

あなたは（2番目の文字列には、重複する文字が存在しない場合）HashSetのに2番目の文字列を変換するために選択することができます

。次に、ハッシュマップの最初の文字列から各文字の存在を確認し、見つかった場合は削除します。

文字列をトラバースするためのO（N）複雑さと、HashSetのput/getの複雑さはほぼO（1）です。

Answer 3

ソース文字列のすべての文字が小文字の場合は、サイズが26のブール値配列を使用できます。 文字列が最初から最後までスキャンし、文字が存在する場合はboolean配列を更新します。 次に、ターゲット文字列をスキャンし、boolean配列がソース配列内にあるかどうかをチェックします。

複雑さは両方の文字列の長さの合計に等しくなります。