Как справиться с временной сложностью перестановки строк при поиске анаграмм?

Question

У меня есть программа, которая вычисляет, являются ли две строки анаграммами или нет. Он отлично работает для ввода строк длиной менее 10. Когда я ввожу две строки, длина которых равна и имеет длину более 10, программа запускается и не дает ответа.

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

Эта программа генерирует все перестановки из одной строки, и после этого она проверяет, есть ли какая-либо соответствующая перестановка для другой строки. В этом случае я хотел игнорировать случаи. Он возвращает false, если не найдено ни одной подходящей строки или строки сравнения не равны по длине, в противном случае возвращает true.

public class Anagrams {

static ArrayList<String> str=new ArrayList<>();

static boolean isAnagram(String a, String b) {


if (a.length() != b.length())  //there is no need for checking these two strings because their length doesn't match
  return false;

Anagrams.permute(a, 0, a.length() - 1);

for (String string:Anagrams.str)
  if(string.equalsIgnoreCase(b))
    return true;  //returns true if there is a matching string for b in the permuted string list of a

return false;  //returns false if there is no matching string for b in the permuted string list of a

}


 private static void permute(String str, int l, int r) {

  if (l == r)  //adds the permuted strings to the ArrayList
    Anagrams.str.add(str);

  else
  {

    for (int i = l; i <= r; i++)
    {
      str = Anagrams.swap(str,l,i);
      Anagrams.permute(str, l+1, r);
      str = Anagrams.swap(str,l,i);
    }

  }

}

public static String swap(String a, int i, int j) {

  char temp;
  char[] charArray = a.toCharArray();
  temp = charArray[i] ;
  charArray[i] = charArray[j];
  charArray[j] = temp;
  return String.valueOf(charArray);

}

}

1 Я хочу знать почему эта программа не может обрабатывать большие строки

2 Я хочу знать, как решить эту проблему

Можете ли вы разобраться?

Answer 1

Чтобы решить эту проблему и проверить, являются ли две строки анаграммами, вам на самом деле не нужно генерировать каждую перестановку исходной строки, а затем сопоставлять ее со второй. Вместо этого вы можете подсчитать частоту каждого символа в первой строке, а затем проверить, применима ли та же частота ко второй строке.

Приведенное выше решение требует один проход для каждой строки, следовательно, Θ (n) сложность по времени. Кроме того, вам нужно вспомогательное хранилище для подсчета символов, которое составляет Θ (1) сложности пространства. Это асимптотически точные границы.

Answer 2

вы делаете это очень дорогим способом, и сложность времени здесь экспоненциальная, потому что вы используете перестановки, которые требуют факториалов и факториалов, очень быстро растут, так как вы делаете перестановки, потребуется время, чтобы получить результат, когда входное значение больше 10.

11 factorial = 39916800 12 factorial = 479001600 13 factorial = 6227020800

и так далее ...

Так что не думайте, что вы не получите вывод для больших чисел, вы будете в итоге получим

Если вы go что-то вроде 20-30 факториала, я думаю, что мне потребуются годы, чтобы произвести какой-либо вывод, если вы используете циклы, с рекурсией вы переполните стек.

факт: 50 факториал - это число, которое больше, чем число зерен песка на земле, и компьютер сдается, когда им приходится иметь дело с такими большими числами.

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

Так что вам не нужно и не следует делать это, чтобы решить эту проблему (потому что компьютер не очень хорош в этом) , это излишество

почему бы вам не взять каждый символ из одной строки и сопоставить его с каждым символом другой строки, в худшем случае это будет квадратичное значение c.

И если вы отсортируете обе строки, вы можете просто скажем

string1.equals(string2)

true означает анаграмма

false означает не анаграмма

и это займет линейное время, кроме времени, затраченного на сортировку.