java - 如何在 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[] 之后)，然后简单的相等性测试将告诉您原始字符串是否为排列。

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