1. Wstęp
W tym artykule zobaczymy, jak za pomocą Javy sprawdzić, czy dany ciąg jest palindromem.
Palindrom to słowo, fraza, liczba lub inna sekwencja znaków, które czyta się tak samo od tyłu jak do przodu , na przykład „pani” lub „samochód wyścigowy”.
2. Rozwiązania
W następnych sekcjach przyjrzymy się różnym sposobom sprawdzenia, czy dany ciąg jest palindromem, czy nie.
2.1. Proste podejście
Możemy jednocześnie rozpocząć iterację danego ciągu do przodu i do tyłu, po jednym znaku na raz. Jeśli jest dopasowanie, pętla jest kontynuowana; w przeciwnym razie pętla kończy pracę:
public boolean isPalindrome(String text) { String clean = text.replaceAll("\\s+", "").toLowerCase(); int length = clean.length(); int forward = 0; int backward = length - 1; while (backward > forward) { char forwardChar = clean.charAt(forward++); char backwardChar = clean.charAt(backward--); if (forwardChar != backwardChar) return false; } return true; }2.2. Odwracanie struny
Istnieje kilka różnych implementacji, które pasują do tego przypadku użycia: podczas sprawdzania palindromów możemy skorzystać z metod API z klas StringBuilder i StringBuffer lub możemy odwrócić String bez tych klas.
Przyjrzyjmy się najpierw implementacjom kodu bez pomocniczych interfejsów API:
public boolean isPalindromeReverseTheString(String text) { StringBuilder reverse = new StringBuilder(); String clean = text.replaceAll("\\s+", "").toLowerCase(); char[] plain = clean.toCharArray(); for (int i = plain.length - 1; i >= 0; i--) { reverse.append(plain[i]); } return (reverse.toString()).equals(clean); }W powyższym fragmencie po prostu wykonujemy iterację danego String od ostatniego znaku i dołączamy każdy znak do następnego znaku, aż do pierwszego znaku, odwracając tym samym dany String.
Na koniec testujemy pod kątem równości między podanym ciągiem a odwróconym ciągiem.
To samo zachowanie można osiągnąć za pomocą metod API.
Zobaczmy szybką demonstrację:
public boolean isPalindromeUsingStringBuilder(String text) { String clean = text.replaceAll("\\s+", "").toLowerCase(); StringBuilder plain = new StringBuilder(clean); StringBuilder reverse = plain.reverse(); return (reverse.toString()).equals(clean); } public boolean isPalindromeUsingStringBuffer(String text) { String clean = text.replaceAll("\\s+", "").toLowerCase(); StringBuffer plain = new StringBuffer(clean); StringBuffer reverse = plain.reverse(); return (reverse.toString()).equals(clean); }We fragmencie kodu wywołujemy metodę reverse () z interfejsu API StringBuilder i StringBuffer w celu odwrócenia danego ciągu znaków i sprawdzenia pod kątem równości.
2.3. Korzystanie z interfejsu Stream API
Możemy również użyć IntStream, aby zapewnić rozwiązanie:
public boolean isPalindromeUsingIntStream(String text) { String temp = text.replaceAll("\\s+", "").toLowerCase(); return IntStream.range(0, temp.length() / 2) .noneMatch(i -> temp.charAt(i) != temp.charAt(temp.length() - i - 1)); }We fragmencie powyżej, stwierdzamy, że żadna z par znaków z każdego końca String spełnia predykat warunek.
2.4. Korzystanie z rekursji
Rekursja jest bardzo popularną metodą rozwiązywania tego typu problemów. W przedstawionym przykładzie rekurencyjnie iterujemy dany ciąg i testujemy, aby dowiedzieć się, czy jest to palindrom, czy nie:
public boolean isPalindromeRecursive(String text){ String clean = text.replaceAll("\\s+", "").toLowerCase(); return recursivePalindrome(clean,0,clean.length()-1); } private boolean recursivePalindrome(String text, int forward, int backward) { if (forward == backward) { return true; } if ((text.charAt(forward)) != (text.charAt(backward))) { return false; } if (forward < backward + 1) { return recursivePalindrome(text, forward + 1, backward - 1); } return true; }3. Wniosek
W tym krótkim samouczku zobaczyliśmy, jak dowiedzieć się, czy dany ciąg jest palindromem, czy nie.
Jak zawsze, przykłady kodu dla tego artykułu są dostępne w serwisie GitHub.