2つの文字列がO（n）時間にお互いの順列であるかどうかを確認する方法はありますか？ （java）

Question

2つの指定された文字列が互いの順列であるかどうかをチェックできるこのクラスを書きました。しかし、string.indexOf（）がO（n）の時間に実行されるため、これはO（n^2）の時間に実行されることは私の理解です。

どのようにしてこのプログラムを効率化できますか？

import java.util.*; 

public class IsPermutation{ 
    public void IsPermutation(){ 
     System.out.println("Checks if two strings are permutations of each other."); 
     System.out.println("Call the check() method"); 
    } 

    public boolean check(){ 
     Scanner console = new Scanner(System.in); 
     System.out.print("Insert first string: "); 
     String first = console.nextLine(); 
     System.out.print("Insert second string: "); 
     String second = console.nextLine(); 

     if (first.length() != second.length()){ 
     System.out.println("Not permutations"); 
     return false; 
     } 

     for (int i = 0; i < first.length(); i++){ 
     if (second.indexOf(first.charAt(i)) == -1){ 
      System.out.println("Not permutations"); 
      return false; 
     } 
     } 
     System.out.println("permutations"); 
     return true; 
    } 
} 

Answer 1

O（n）をアーカイブする1つの方法は、すべての文字の頻度を数えることです。

私はHashMapをキーとして使用し、frequencysは値として使用します。すべての文字の周波数が同じ

//runtime O(3*n) = O(n) 
public boolean compare(String s1, String s2){ 
    if(s1.length() != s2.length()){ 
     return false; 
    } 

    //runtime O(n) 
    HashMap<Character, Integer> map1 = getFrequencys(s1); 
    HashMap<Character, Integer> map2 = getFrequencys(s2); 

    //Iterate over every character in map1 (every character contained in s1) (runtime O(n)) 
    for(Character c : map1.keySet()){ 
     //if the characters frequencys are different, the strings arent permutations 
     if(map2.get(c) != map1.get(c)){ 
      return false; 
     } 
    } 

    //since every character in s1 has the same frequency in s2, 
    //and the number of characters is equal => s2 must be a permutation of s1 

    return true; 
} 

編集がある場合

//create a HashMap containing the frequencys of every character of the String (runtime O(n)) 
public HashMap<Character, Integer> getFrequencys(String s){ 
    HashMap<Character, Integer> map = new HashMap<>(); 

    for(int i=0; i<s.length(); i++){ 
     //get character at position i 
     char c = s.charAt(i); 

     //get old frequency (edited: if the character is added for the 
     //first time, the old frequency is 0) 
     int frequency; 
     if(map.containsKey(c)){ 
      frequency = map.get(c); 
     }else{ 
      frequency = 0; 
     } 
     //increment frequency by 1 
     map.put(c, frequency+1); 
    } 

    return map; 
} 

は今、あなたは、両方の文字列のHashMapを作成し、比較することができます：（未テスト）コードでnullポインタエラーが発生した

Answer 2

まず、それは（char[]に変換後の）2つの文字列をソートすることによってO(nlogn)で行うことができ、元の文字列が置換されているかいないならば、単純な等価テストはあなたを教えてくれます。

O(n)HashMap<Character, Integer>を作成することで解を平均化することができます。各キーは文字列内の文字で、値は出現回数です（これはHistogramと呼ばれます）。あなたがそれを持っていれば、再び元の文字列が置換であるかどうかを2つのマップの単純な等価チェックで知ることができます。

Answer 3

ソート対策：

public void IsPermutation(String str1, String str2) { 
    char[] sortedCharArray1 = Arrays.sort(str1.toCharArray()); 
    char[] sortedCharArray2 = Arrays.sort(str2.toCharArray()); 

    return Arrays.equals(sortedCharArray1, sortedCharArray2); 
} 

時間複雑度：O（N Nログ） スペースの複雑さ：O（n）の

周波数カウントソリューション：

//Assuming that characters are only ASCII. The solutions can easily be modified for all characters 

public void IsPermutation(String str1, String str2) { 
    if (str1.length() != str2.length()) 
     return false; 

    int freqCountStr1[] = new int[256]; 
    int freqCountStr2[] = new int[256]; 

    for (int i = 0; i < str1.length(); ++i) { 
     int c1 = str1.charAt(i); 
     int c2 = str2.charAt(i); 
     ++freqCountStr1[c1]; 
     ++freqCountStr2[c2]; 
    } 

    for (int i = 0; i < str1.length(); ++i) { 
     if (freqCountStr1[i] != freqCountStr2[i]) { 
      return false; 
     } 
    } 

    return true; 
    } 
} 

時間計算：O（n）の スペース複雑さ：、それはO（256）