Алгоритм анаграммы с минимальной сложностью

Question

Недавно меня попросили разработать алгоритм, который проверяет, являются ли две строки анаграммами друг друга. Моя цель состояла в том, чтобы минимизировать пространство и временную сложность, поэтому я придумал этот алгоритм:

1. Создать массив из 26 элементов, каждый из которых инициализируется нулем.
2. Пройдите первую строку и для каждого символа увеличьте значение элемента массива, соответствующего этому символу.
3. Пройдите по второй строке и для каждого символа уменьшите элемент массива, соответствующий этому символу.
4. Сканирование массива. Если все элементы равны 0, две строки являются анаграммами.

Однако временная сложность этого алгоритма составляет O (n), и я не могу придумать алгоритм с меньшей сложностью. Кто-нибудь знает об этом?

Answer 1

Ваш алгоритм асимптотически оптимален.Невозможно решить эту проблему лучше, чем за время (n).Чтобы убедиться в этом, предположим, что существует алгоритм A, который может решить проблему за o (n) времени (обратите внимание, что здесь мало n из n).Тогда для любого 1> ε> 0 существует такое n, что для любого входа размером не менее n алгоритм должен завершаться не более чем на εn шагов.Установите ε = 1/3 и рассмотрите любые входные данные для алгоритма, имеющие длину не менее n для вышеупомянутого n для этого ε.Поскольку алгоритм может просматривать не более 1/3 символов в двух строках, то для функции должно быть два разных входа: один - пара анаграмм, а другой - нет, чтобы алгоритм смотрелто же подмножество символов каждого входа.В этом случае функция должна была бы выдавать один и тот же вывод в каждом случае, и, таким образом, она была бы неправильной, по крайней мере, на одном из входов.Мы достигли противоречия, поэтому такой алгоритм не должен существовать.

Answer 2

Вы можете улучшить среднюю производительность при ранних выходах. При сканировании 2-й строки, если count [char] равно 0, прежде чем вы уменьшите, у вас нет анаграммы, и вы можете остановить сканирование.

Кроме того, если строки короче, чем 26 символов, то на последнем шаге проверяйте нули только на символах в первой строке.

Это не меняет большой O, но может изменить среднее время выполнения на что-то меньшее, чем 2N + 26 o предлагаемого решения, в зависимости от ваших данных.

Answer 3

Чтобы убедиться, что строки являются анаграммами, вам нужно сравнить целые строки - так как это может быть быстрее, чем o (n)?

Answer 4

Давайте ответим на вопрос: Учитывая две строки s и t, напишите функцию, чтобы определить, является ли t анаграммой s.

Например, s = "anagram", t = "nagaram", вернуть true. s = "крыса", t = "машина", возврат false.

Метод 1 (с использованием HashMap):

    public class Method1 {

    public static void main(String[] args) {
        String a = "protijayi";
        String b = "jayiproti";
        System.out.println(isAnagram(a, b ));// output => true

    }

    private static boolean isAnagram(String a, String b) {
        Map<Character ,Integer> map = new HashMap<>();
        for( char c : a.toCharArray()) {
            map.put(c,    map.getOrDefault(c, 0 ) + 1 );
        }
        for(char c : b.toCharArray()) {
            int count = map.getOrDefault(c, 0);
            if(count  == 0 ) {return false ; }
            else {map.put(c, count - 1 ) ; }
        }

        return true;
    }

}

Метод 2:

    public class Method2 {
public static void main(String[] args) {
    String a = "protijayi";
    String b = "jayiproti";


    System.out.println(isAnagram(a, b));// output=> true
}

private static boolean isAnagram(String a, String b) {


    int[] alphabet = new int[26];
    for(int i = 0 ; i < a.length() ;i++) {
         alphabet[a.charAt(i) - 'a']++ ;
    }
    for (int i = 0; i < b.length(); i++) {
         alphabet[b.charAt(i) - 'a']-- ;
    }

    for(  int w :  alphabet ) {
         if(w != 0 ) {return false;}
    }
    return true;

}
}

Метод 3:

    public class Method3 {
public static void main(String[] args) {
    String a = "protijayi";
    String b = "jayiproti";


    System.out.println(isAnagram(a, b ));// output => true
}

private static boolean isAnagram(String a, String b) {
    char[] ca = a.toCharArray() ;
    char[] cb = b.toCharArray();
    Arrays.sort(   ca     );

    Arrays.sort(   cb        );
    return Arrays.equals(ca , cb );
}
}

Метод 4:

    public class Method4 {
public static void main(String[] args) {
    String a = "protijayi";
    String b = "jayiproti";
    //String c = "gini";

    System.out.println(isAnagram(a, b ));// output => true
}

private static boolean isAnagram(String a, String b) {
    Map<Integer, Integer> map = new HashMap<>();
    a.codePoints().forEach(code -> map.put(code, map.getOrDefault(code, 0) + 1));
    b.codePoints().forEach(code -> map.put(code, map.getOrDefault(code, 0) - 1));
    //System.out.println(map.values());

    for(int count : map.values()) {
       if (count<0) return false;

    }

    return true;
}
}

Answer 5

int anagram (char a[], char b[]) {

  char chars[26];
  int ana = 0;
  int i =0;

  for (i=0; i<26;i++)
        chars[i] = 0;


  if (strlen(a) != strlen(b))
        return -1;

  i = 0;
  while ((a[i] != '\0') || (b[i] != '\0')) {
        chars[a[i] - 'a']++;
        chars[b[i] - 'a']--;
        i++;
  }

  for (i=0; i<26;i++)
        ana += chars[i];

   return ana;

}


void main() {

  char *a = "chimmy\0";
  char *b = "yimmch\0";

  printf ("Anagram result is %d.\n", anagram(a,b));


}