np. „ccddcc” w ciągu „abaccddccefe”
Pomyślałem o rozwiązaniu, ale działa ono w czasie O (n ^ 2)
Algo 1:
Kroki: To metoda brutalnej siły
- Miej 2 pętle
for dla i = 1 do i mniej niż array.length -1
dla j = i + 1 do j mniej niż array.length - W ten sposób możesz uzyskać podciąg każdej możliwej kombinacji z tablicy
- Miej funkcję palindromową, która sprawdza, czy łańcuch jest palindromem
- więc dla każdego podciągu (i, j) wywołaj tę funkcję, jeśli jest to palindrom, zapisz ją w zmiennej łańcuchowej
- Jeśli znajdziesz następny podciąg palindromu i jeśli jest większy niż bieżący, zastąp go bieżącym.
- Wreszcie twoja zmienna łańcuchowa będzie miała odpowiedź
Problemy: 1. Ten algorytm działa w czasie O (n ^ 2).
Algo 2:
- Odwróć ciąg i zapisz go w innej tablicy
- Teraz znajdź największy pasujący podciąg między obiema tablicami
- Ale to też przebiega w czasie O (n ^ 2)
Czy możecie pomyśleć o algo, które działa w lepszym czasie. Jeśli to możliwe, czas O (n)
algorithm
palindrome
Uczeń
źródło
źródło
O(n^2)
pobranie podciągów *,O(n)
aby sprawdzić, czy są to palindromy, w sumieO(n^3)
?Odpowiedzi:
Możesz znaleźć najdłuższy palindrom za pomocą algorytmu Manachera w
O(n)
czasie! Jego implementację można znaleźć tutaj i tutaj .Dla danych wejściowych
String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE"
znajduje prawidłowe wyjście, którym jest1234567887654321
.źródło
while
osadzony wfor
z ograniczeniem, które wydaje się podobne do zewnętrznej pętli.Algo 2 może nie działać dla wszystkich ciągów. Oto przykład takiego ciągu „ABCDEFCBA”.
Nie chodzi o to, że łańcuch ma „ABC” i „CBA” jako podciąg. Jeśli odwrócisz oryginalny ciąg, będzie to „ABCFEDCBA”. a najdłuższym pasującym podciągiem jest „ABC”, który nie jest palindromem.
Może być konieczne dodatkowe sprawdzenie, czy ten najdłuższy pasujący podciąg jest w rzeczywistości palindromem, którego czas działania wynosi O (n ^ 3).
źródło
O ile zrozumiałem problem, możemy znaleźć palindromy wokół środkowego indeksu i rozciągnąć nasze poszukiwania w obie strony, na prawo i lewo od środka. Biorąc to pod uwagę i wiedząc, że w rogach wejścia nie ma palindromu, możemy ustawić granice na 1 i długość-1. Zwracając uwagę na minimalne i maksymalne granice łańcucha, sprawdzamy, czy znaki na pozycjach indeksów symetrycznych (prawy i lewy) są takie same dla każdej pozycji centralnej, aż osiągniemy maksymalny górny środek ograniczający.
Pętla zewnętrzna to O (n) (max n-2 iteracji), a wewnętrzna pętla while to O (n) (max około (n / 2) - 1 iteracja)
Oto moja implementacja Java na przykładzie dostarczonym przez innych użytkowników.
Wynik tego jest następujący:
źródło
expandAroundCenter
.za pomocą wyrażeń regularnych i ruby możesz szukać krótkich palindromów, takich jak ten:
źródło
Poniższy program w Javie napisałem z ciekawości, prosty i nie wymagający wyjaśnień HTH. Dzięki.
źródło
Ostatnio zadano mi to pytanie. Oto rozwiązanie, które [ostatecznie] wymyśliłem. Zrobiłem to w JavaScript, ponieważ jest to dość proste w tym języku.
Podstawową koncepcją jest to, że idziesz po łańcuchu w poszukiwaniu najmniejszego możliwego palindromu wieloznakowego (dwu- lub trzyznakowego). Gdy już to zrobisz, rozszerz granice po obu stronach, aż przestanie być palindromem. Jeśli ta długość jest dłuższa niż obecnie najdłuższa, zapisz ją i przejdź dalej.
Zdecydowanie można to nieco bardziej oczyścić i zoptymalizować, ale powinno mieć całkiem dobrą wydajność we wszystkich scenariuszach oprócz najgorszego przypadku (ciąg tej samej litery).
źródło
i
j
l
s
if
i utrzymywane w stanie. wiele punktów zwrotnych,Cześć Oto mój kod, aby znaleźć najdłuższy palindrom w ciągu. Prosimy zapoznać się z poniższym linkiem, aby zrozumieć algorytm http://stevekrenzel.com/articles/longest-palnidrome
Użyte dane testowe to HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
źródło
Zobacz artykuł w Wikipedii na ten temat. Przykładowa implementacja algorytmu Java firmy Manacher dla liniowego rozwiązania O (n) z artykułu poniżej:
źródło
Skuteczne
Regexp
rozwiązanie, które pozwala uniknąć brutalnej siłyRozpoczyna się od całej długości łańcucha i działa w dół do 2 znaków, istnieje zaraz po dopasowaniu
Dla
"abaccddccefe"
testów regexp 7 dopasowań przed powrotemccddcc
.vbs
vba
funkcjonować
źródło
źródło
Wypróbuj ciąg - "HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE"; Powinien działać dla parzystych i nieparzystych kumpli. Wielkie dzięki dla Mohita!
using namespace std;
źródło
isPal
- operację O (n) - tylko po to, by zmierzyć jej długość !? Ma również wadliwą próbę radzenia sobie nawet z palindromami. W przypadku błędu z parzystym palindromem:else if(input_str[i] == input_str[j])
nigdy nie może się powieść, ponieważ ten sam test musiał zakończyć się niepowodzeniem w poprzedniejif
instrukcji; i tak jest wadliwy, ponieważ po prostu patrząc na 2 znaki oddalone od siebie o 2 pozycje nie można stwierdzić, czy patrzysz na parzysty czy nieparzysty palindrom (rozważAAA
iAAAA
).Poniższy kod oblicza Palidrom dla ciągów o parzystej i nieparzystej długości.
Nie jest to najlepsze rozwiązanie, ale działa w obu przypadkach
HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE
źródło
Za pomocą tego możemy znaleźć wszystkie palindromy dowolnej długości.
Próbka:
słowo = abcdcbc
modifiedString = a # b # c # d # c # b # c
palinCount = 1010105010301
długość najdłuższego palindromu = 5;
najdłuższy palindrom = bcdcb
public class MyLongestPalindrome {
}
źródło
To zwróci najdłuższy łańcuch palindromowy z podanego ciągu
== WYJŚCIE ===
Wejście: abcccde Wyjście: ccc
Dane wejściowe: abcccbd Dane wyjściowe: bcccb
Wejście: abedccde Wyjście: edccde
Dane wejściowe: abcccdeed Dane wyjściowe: akt
Dane wejściowe: abcccbadeed Dane wyjściowe: abcccba
źródło
Oto implementacja w javascript:
źródło
W przypadku rozwiązania liniowego można użyć algorytmu Manachera. Istnieje inny algorytm nazywający algorytm Gusfielda, a poniżej jest kod w java:
Więcej o innych rozwiązaniach, takich jak najlepsze rozwiązanie O (n ^ 2) czy algorytm Manachera, można znaleźć na moim blogu .
źródło
Tutaj napisałem logikę, spróbuj :)
źródło
To rozwiązanie ma złożoność O (n ^ 2). O (1) to złożoność przestrzeni.
źródło
{'DED': 3, '123456789987654321': 18, '67899876': 8, 'ABCDEDCBA': 9, '456789987654': 12, '34567899876543': 14, 'BCDEDCB': 7, 'ABA': 3, ' 5678998765 ': 10,' 2345678998765432 ': 16,' CDEDC ': 5,' 789987 ': 6,' 8998 ': 4} (' 123456789987654321 ', 18)
źródło
Oto mój algorytm:
1) ustaw bieżące centrum na pierwszą literę
2) jednocześnie rozszerzaj się w lewo iw prawo, aż znajdziesz maksymalny palindrom wokół aktualnego środka
3) jeśli znaleziony palindrom jest większy niż poprzedni, zaktualizuj go
4) ustaw bieżące centrum na następną literę
5) powtórz kroki od 2) do 4) dla wszystkich liter w ciągu
To działa w O (n).
Mam nadzieję, że to pomoże.
źródło
Źródła: Wikipedia.com
Najlepszy algorytm, jaki kiedykolwiek znalazłem, ze złożonością O (N)
źródło
moje rozwiązanie to:
źródło
Substring()
i string-equality (==
). Jest to w zasadzie identyczny algorytm OP nr 1.