Учитывая две строки, как вы можете проверить, являются ли они перестановкой друг друга, используя пространство O (1)? Модификация строк никоим образом не допускается.
Примечание: O (1) пробел по отношению как к длине строки, так и к размеру алфавита.
algorithms
strings
space-complexity
анонимное
источник
источник
O(log n)
для строк длины n, которая не является ни постоянной по длине, ни по размеру алфавита. Когда строки могут быть временно изменены, я думаю, что есть решение с увеличенным алфавитом, который является линейным по размеру алфавита, но постоянным по длине строки в логарифмической модели.Ответы:
Наивным подходом было бы построение гистограмм обеих строк и проверка их одинаковости. Так как нам не разрешено хранить такую структуру данных (размер которой был бы линейным по отношению к размеру алфавита), который мог бы быть вычислен за один проход, нам нужно подсчитать количество каждого возможного символа после другого:
Это, конечно, предполагает, что счетчики и индексы итераторов являются целыми числами постоянного размера, а не зависят от длины строк.
источник
O(n * min(n, |Σ|))
. Хм, теперь, когда я думаю об этом, это звучит как «разрешено повторить» решение из вашего ответа, не так ли?count
нетO(1)
(то есть может переполниться)count
былоint
:-) Да, это не будет работать, но в Java , что не может случиться так или иначеОбозначим массивы через и предположим, что они имеют длину n .А , Б N
Предположим сначала, что значения в каждом массиве различны. Вот алгоритм, который использует пространство :O ( 1 )
Вычислите минимальные значения обоих массивов и убедитесь, что они идентичны.
Вычислите вторые минимальные значения обоих массивов и убедитесь, что они идентичны.
И так далее.
Для вычисления минимального значения массива явно используется пространство . Учитывая k- й наименьший элемент, мы можем найти ( k + 1 ) -й наименьший элемент, найдя минимальное значение, превышающее k- й наименьший элемент (здесь мы используем тот факт, что все элементы различны).O ( 1 ) К ( к + 1 ) К
Когда элементам разрешено повторяться, мы модифицируем алгоритм следующим образом:
Вычислите минимальные значения для обоих массивов, посчитайте, сколько раз каждый из них появляется, и проверьте, что m A , 1 = m B , 1 и что значения идентичны.мА , 1, мБ , 1 мА , 1= мБ , 1
Вычислите минимальные значения превышающие m A , 1 , m B , 1 в двух массивах (соответственно), и подсчитайте, сколько раз каждый из них появляется. Убедитесь, что m A , 2 = m B , 2 и что количество идентичных.мА , 2, мБ , 2 мА , 1, мБ , 1 мА , 2= мБ , 2
И так далее.
источник
Определите некоторую функцию f (c), которая отображает некоторый символ c на уникальное простое число (a = 2, b = 3, c = 5 и т. Д.).
источник
Вы можете сделать этоO(nlogn)
. Сортируйте две строки и сравнивайте их индекс по индексу. Если они где-то отличаются, они не являются перестановками друг друга.Для
O(n)
решения проблемы можно использовать хеширование. Эта функция хеширования будет работать, иe
для любой буквы будет ее значение ascii. Если два хэша строк различаются, они не являются перестановками друг друга.Функция хеширования в ссылке:
Использование двойного хеширования (или даже для избыточного убийства) путем изменения значения R успешно идентифицирует их как перестановки с очень высокой вероятностью.
источник
Допустим, у вас есть две строки с именами s и t.
Вы можете использовать эвристику, чтобы убедиться, что они не являются неравными.
После этого вы можете легко запустить алгоритм, чтобы доказать, что строки равны.
Конечно, вы не можете сортировать так быстро, если вам не разрешено использовать дополнительное пространство. Таким образом, не имеет значения, какой алгоритм вы выберете - каждый алгоритм будет нуждаться в O (n ^ 2) времени, когда есть только O (1) пространство и если эвристика не смогла доказать, что они не могут быть равны.
источник
В коде в стиле C для всей процедуры:
Или в очень подробном псевдокоде (с использованием индексации на основе 1)
где функция checkLetters (A, B, i) проверяет, что если в A [1] .. A [i] имеется M копий A [i], то в B имеется как минимум M копий A [i]:
и функция findNextValue ищет в B значение, начинающееся с индекса, и возвращает индекс, где оно было найдено (или n + 1, если не найдено).
Идея в том, что мы уже проверили, что у нас есть перестановка символов перед i во внешнем цикле. В цикле j мы проходим все символы, которые соответствуют A [i], и мы должны быть в состоянии найти уникальные индексы в B, которые соответствуют им (включая i-ую позицию). Таким образом, для каждого из них нам нужно продвинуть наше сканирование вперед через B. Время равно O (N2 ).
источник
Я думаю, что это самый простой алгоритм (сO ( n3 ) время, N длина струн)
Цикл
string1
иstring2
, для каждого символа, проверьте, как часто он может быть найден вstring1
иstring2
. Если символ находится в одной строке чаще, чем в другой, это не перестановка. Если частоты всех символов равны, то строки являются перестановками друг друга.Вот кусок питона, чтобы сделать это точным
Программа нуждается в некоторых указателях на строки (O ( журналн ) для подсчета (
string
,string1
,string2
,char
,char1
,char2
) и переменного размераcount1
,count2
). Нужно проверить, равны ли символы или нет, но не нужно упорядочивать эти символы. Возможно, для небольших целых чисел нужны переменные (например, для хранения логических значений или для представления позицииstring
в[string1, string2]
.Конечно, вам даже не нужны переменные count, но вы можете использовать указатели.
Эта вторая программа нуждается в переменных, аналогичных первой, за исключением того, что она не нуждается вO ( журнал( н ) ) переменные для хранения значений счетчика.
Так что на самом деле это не зависит отN или размер алфавита.
источник