如何在O(n)时间内检查两个字符串是否互为排列?(java)

Question

我编写了这个类，它可以检查两个给定的字符串是否是彼此的排列。然而，我的理解是，这运行在O(n^2)时间，因为string.indexOf()运行在O(n)时间。

如何使这个程序更有效率?

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(nlogn)中通过对两个字符串排序(在将它们转换为char[]之后)来完成，然后简单的相等性测试将告诉您原始字符串是否是排列。

可以通过创建HashMap<Character, Integer>来实现O(n)解的平均情况，其中每个键是字符串中的一个字符，值是其出现的次数(这称为直方图)。完成后，对两个映射进行简单的相等性检查将告诉您原始字符串是否是排列。

Answer 2

存档O(n)的一种方法是计算每个字符的频率。

我将使用一个HashMap，其中字符作为键，频率作为值。

//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并比较每个字符的频率是否相同

//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;
}

编辑:在(未测试的)代码

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 log 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)空间复杂度:0 (256)