Biorąc pod uwagę dwa ciągi, jak możesz sprawdzić, czy są one wzajemną permutacją za pomocą spacji O (1)? Modyfikowanie ciągów znaków nie jest w żaden sposób dozwolone.
Uwaga: odstęp O (1) w stosunku do długości łańcucha ORAZ wielkości alfabetu.
algorithms
strings
space-complexity
Anonimowy
źródło
źródło
O(log n)
ciągów o długości n, która nie jest stała ani za pomocą długości, ani wielkości alfabetu. Kiedy łańcuchy mogą być tymczasowo modyfikowane, myślę, że istnieje rozwiązanie ze zwiększonym alfabetem, który jest liniowy w rozmiarze alfabetu, ale stały w długości łańcucha w modelu logarytmicznym.Odpowiedzi:
Naiwnym podejściem byłoby budowanie histogramów obu ciągów i sprawdzanie, czy są one takie same. Ponieważ nie wolno nam przechowywać takiej struktury danych (której rozmiar byłby liniowy do wielkości alfabetu), którą można by obliczyć w jednym przebiegu, musimy policzyć wystąpienia każdego możliwego symbolu po drugim:
Zakłada się oczywiście, że liczby i wskaźniki iteratora są liczbami całkowitymi o stałym rozmiarze, a nie zależą od długości łańcuchów.
źródło
O(n * min(n, |Σ|))
. Hm, teraz, kiedy o tym myślę, brzmi to jak rozwiązanie „dozwolone do powtórzenia” z twojej odpowiedzi, prawda?count
nie jestO(1)
(tzn. może się przepełnić)count
byłint
:-) Tak, to nie praca, ale w Javie , że nie może się zdarzyć w każdym razieOznacz tablice i załóżmy, że mają długość n .A , B n
Załóżmy najpierw, że wartości w każdej tablicy są różne. Oto algorytm, który wykorzystuje przestrzeń :O ( 1 )
Oblicz minimalne wartości obu tablic i sprawdź, czy są one identyczne.
Oblicz drugie minimalne wartości obu tablic i sprawdź, czy są one identyczne.
I tak dalej.
Obliczenie minimalnej wartości tablicy wyraźnie wykorzystuje przestrzeń . Biorąc pod uwagę k- najmniejszy element, możemy znaleźć ( k + 1 ) st najmniejszy element, znajdując minimalną wartość większą niż k- ty najmniejszy element (tutaj wykorzystujemy fakt, że wszystkie elementy są odrębne).O ( 1 ) k ( k + 1 ) k
Gdy elementy mogą się powtarzać, modyfikujemy algorytm w następujący sposób:
Oblicz minimalne wartości obu tablic, policz, ile razy każde z nich się pojawi, i sprawdź m A , 1 = m B , 1 i czy liczby są identyczne.mA , 1, mB , 1 mA , 1= mB , 1
Obliczyć minimalne wartości większe niż m A , 1 , m B , 1 w dwóch tablicach (odpowiednio) i policzyć, ile razy się pojawiają. Sprawdź, czy m A , 2 = m B , 2 i czy liczby są identyczne.mA , 2, mB , 2 mA , 1, mB , 1 mA , 2= mB , 2
I tak dalej.
źródło
Zdefiniuj funkcję f (c), która odwzorowuje znak c na unikalną liczbę pierwszą (a = 2, b = 3, c = 5 itd.).
źródło
Możesz to zrobićO(nlogn)
. Posortuj dwa ciągi i porównaj je indeks po indeksie. Jeśli różnią się gdziekolwiek, to nie są wzajemnymi permutacjami.Dla
O(n)
rozwiązania można zastosować skrót. Ta funkcja mieszająca działałaby ie
dla każdej litery byłaby jej wartość ascii. Jeśli dwa skróty ciągów różnią się, nie są one wzajemnymi permutacjami.Funkcja skrótu w łączu:
Użycie podwójnego haszowania (lub jeszcze większej przepełnienia) poprzez zmianę wartości R z powodzeniem zidentyfikowałoby je jako permutacje z bardzo dużym prawdopodobieństwem.
źródło
Powiedzmy, że masz dwa ciągi zwane s i t.
Możesz użyć heurystyki, aby upewnić się, że nie są one nierówne.
Następnie możesz łatwo uruchomić algorytm, aby udowodnić, że ciąg znaków jest równy.
Oczywiście nie możesz posortować tak szybko, jeśli nie możesz użyć dodatkowej przestrzeni. Nie ma więc znaczenia, który algorytm wybierzesz - każdy algorytm będzie działał w czasie O (n ^ 2), gdy będzie tylko przestrzeń O (1) i jeśli heurystyka nie będzie w stanie udowodnić, że nie mogą być równe.
źródło
W kodzie w stylu C dla całej procedury:
Lub bardzo pseudo-kodem (przy użyciu indeksowania 1)
gdzie funkcja checkLetters (A, B, i) sprawdza, czy jeśli istnieje M kopii A [i] w A [1] .. A [i], to jest co najmniej M kopii A [i] w B:
i funkcja findNextValue wyszukuje w B wartość rozpoczynającą się od indeksu i zwraca indeks, w którym został znaleziony (lub n + 1, jeśli nie został znaleziony).
źródło
Pętla
string1
istring2
dla każdej postaci sprawdź, jak często można ją znaleźć wstring1
istring2
. Jeśli znak jest częściej w jednym ciągu niż w drugim, nie jest to permutacja. Jeśli częstotliwości wszystkich znaków są równe, to łańcuchy są wzajemnymi permutacjami.Oto fragment pytona, aby to precyzyjnie określić
string
string1
string2
char
char1
char2
count1
count2
string
[string1, string2]
Oczywiście nie potrzebujesz nawet zmiennych count, ale możesz używać wskaźników.
źródło