Один из вариантов - подсчитать числа каждого символа в каждой строке и сравнить их. Простая реализация должна занять O(max(N, A)) время, где N - длина самой большой строки, а A - размер массива, который вы используете для хранения счетчиков. Например, в Java:
public boolean equalIgnoringOrder(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
// Assuming characters in the range ASCII 0 to 127
int[] c1 = new int[128];
int[] c2 = new int[128];
for (int i = 0; i < s1.length(); i++) {
c1[s1.charAt(i)]++;
c2[s2.charAt(i)]++;
}
for (int i = 0; i < c1.length; i++) {
if (c1[i] != c2[i]) {
return false;
}
}
return true;
}
Есть несколько возможных улучшений в этом. Например, вы можете справиться с произвольным набором символов, выполнив уменьшение диапазона; то есть сделайте начальный проход через s1 и s2, ища самые маленькие и самые большие символы в каждом из них, и используйте это, чтобы определить размер c1 и c2 и базовое смещение. Это в среднем займет меньше места и сократит время на инициализацию массивов подсчета. Это также предлагает короткое замыкание для сравнения; например когда самые маленькие и самые большие символы для s1 и s2 не совпадают.
Для сравнения, сравнение строк, отсортированных с использованием heapsort или quicksort, в среднем составило бы O(NlogN) с пробелом O(N), где N - длина большей строки.
Однако, как указывает @pst, константы пропорциональности могут сделать алгоритм O(NlogN) или даже O(N*N) лучше, чем алгоритм O(N), если N невелико. В этом случае средняя длина сравниваемых строк, вероятно, является наиболее важным фактором.
Приведенный выше код эффективно выполняет сортировку по Radix с парой коротких замыканий. (Три, если вы включите короткое замыкание, связанное с уменьшением диапазона.) Таким образом, в конечном итоге все сводится к тому, будет ли лучше быстрая сортировка / сортировка по кучи или сортировка по радиксу. И это зависит от длины входной строки и диапазонов символов.
На другом галсе. @ В ответе Джона предлагается вычислить произведение простых чисел. Если мы выполняем вычисления с использованием представления произвольной точности, результирующие значения будут уникальными для каждого отдельного набора строк «равного порядка игнорирования». К сожалению, вычисление будет O(N*N). (Каждый промежуточный продукт имеет O(N) цифр, а умножение N-значного числа на константу составляет O(N). Сделайте это для N символов, и вы получите O(N*N).)
Но если мы сделаем вычисление по модулю (скажем) 64, результатом будет действительно хороший хеш, нечувствительный к порядку символов; например,
long hash = 1;
for (int i = 0; i < s.length(); i++) {
hash = hash * primes[s.charAt(i)];
}
Итак, я бы сказал, что алгоритм, обеспечивающий наилучшую производительность и использование пространства в среднем для сравнения случайно сгенерированных строк, вероятно, будет иметь вид:
if (s1.length() != s2.length()) {
return false;
}
if (hash(s1) != hash(s2)) { // computed as above
return false;
}
// Compare using sorting or character counting as above.
Один последний момент. Если мы предположим, что строковые указатели не идентичны и строки имеют неодинаковую длину, любой алгоритм, который вычисляет этот equals предикат , должен иметь значение при O(N) или хуже. Он должен проверить каждый символ в обеих строках, чтобы сделать это определение, и для этого требуется O(N) операций.
Любой алгоритм, который выполняет менее 2 * N выборок или менее 2 * N дальнейших операций с извлеченными значениями в этом сценарии доказуемо неверен.