Palindrom to słowo, fraza, numer lub inny ciąg jednostek, które mogą być odczytane w ten sam sposób w obu kierunkach.
Aby sprawdzić, czy słowo jest palindromem, pobieram tablicę znaków tego słowa i porównuję znaki. Przetestowałem to i wydaje się, że działa. Chcę jednak wiedzieć, czy jest to słuszne, czy też jest coś do poprawy.
Oto mój kod:
public class Aufg1 {
public static void main(String[] args) {
String wort = "reliefpfpfeiller";
char[] warray = wort.toCharArray();
System.out.println(istPalindrom(warray));
}
public static boolean istPalindrom(char[] wort){
boolean palindrom = false;
if(wort.length%2 == 0){
for(int i = 0; i < wort.length/2-1; i++){
if(wort[i] != wort[wort.length-i-1]){
return false;
}else{
palindrom = true;
}
}
}else{
for(int i = 0; i < (wort.length-1)/2-1; i++){
if(wort[i] != wort[wort.length-i-1]){
return false;
}else{
palindrom = true;
}
}
}
return palindrom;
}
}
Odpowiedzi:
Dlaczego nie tylko:
public static boolean istPalindrom(char[] word){ int i1 = 0; int i2 = word.length - 1; while (i2 > i1) { if (word[i1] != word[i2]) { return false; } ++i1; --i2; } return true; }
Przykład:
Dane wejściowe to „andna”.
i1 będzie równe 0, a i2 będzie równe 4.
Pierwsza iteracja pętli, którą porównamy
word[0]
iword[4]
. Są równe, więc zwiększamy i1 (teraz jest 1) i zmniejszamy i2 (teraz jest 3).Więc porównujemy n. Są równe, więc zwiększamy i1 (teraz jest 2) i zmniejszamy i2 (to jest 2).
Teraz i1 i i2 są równe (oba są 2), więc warunek pętli while nie jest już prawdziwy, więc pętla się kończy i zwracamy wartość true.
źródło
Możesz sprawdzić, czy ciąg jest palindromem, porównując go z jego odwrotnością:
public static boolean isPalindrome(String str) { return str.equals(new StringBuilder(str).reverse().toString()); }
lub dla wersji Java starszych niż 1.5,
public static boolean isPalindrome(String str) { return str.equals(new StringBuffer().append(str).reverse().toString()); }
EDYCJA: @FernandoPelliccioni przedstawił bardzo dokładną analizę wydajności (lub jej braku) tego rozwiązania, zarówno pod względem czasu, jak i przestrzeni. Jeśli interesuje Cię złożoność obliczeniowa tego i inne możliwe rozwiązania tego pytania, przeczytaj to!
źródło
Zwięzła wersja, która nie wymaga (nieefektywnej) inicjalizacji wielu obiektów:
boolean isPalindrome(String str) { int n = str.length(); for( int i = 0; i < n/2; i++ ) if (str.charAt(i) != str.charAt(n-i-1)) return false; return true; }
źródło
Alternatywnie, rekurencja .
Dla każdego, kto szuka krótszego rozwiązania rekurencyjnego, aby sprawdzić, czy dany ciąg spełnia wymagania jako palindrom:
private boolean isPalindrome(String s) { int length = s.length(); if (length < 2) // If the string only has 1 char or is empty return true; else { // Check opposite ends of the string for equality if (s.charAt(0) != s.charAt(length - 1)) return false; // Function call for string with the two ends snipped off else return isPalindrome(s.substring(1, length - 1)); } }
LUB jeszcze krócej , jeśli chcesz:
private boolean isPalindrome(String s) { int length = s.length(); if (length < 2) return true; return s.charAt(0) != s.charAt(length - 1) ? false : isPalindrome(s.substring(1, length - 1)); }
źródło
return s.charAt(0) == s.charAt(l - 1) && isPalindrome(s.substring(1, l - 1));
Idź, Java:
public boolean isPalindrome (String word) { String myWord = word.replaceAll("\\s+",""); String reverse = new StringBuffer(myWord).reverse().toString(); return reverse.equalsIgnoreCase(myWord); } isPalindrome("Never Odd or Even"); // True isPalindrome("Never Odd or Even1"); // False
źródło
także inne wyglądające rozwiązanie:
public static boolean isPalindrome(String s) { for (int i=0 , j=s.length()-1 ; i<j ; i++ , j-- ) { if ( s.charAt(i) != s.charAt(j) ) { return false; } } return true; }
źródło
A oto kompletne rozwiązanie do przesyłania strumieniowego Java 8 . IntStream zapewnia wszystkie indeksy til długości struny pół, a następnie Porównanie od początku i od końca jest wykonywana.
public static void main(String[] args) { for (String testStr : Arrays.asList("testset", "none", "andna", "haah", "habh", "haaah")) { System.out.println("testing " + testStr + " is palindrome=" + isPalindrome(testStr)); } } public static boolean isPalindrome(String str) { return IntStream.range(0, str.length() / 2) .noneMatch(i -> str.charAt(i) != str.charAt(str.length() - i - 1)); }
Wynik to:
testing testset is palindrome=true testing none is palindrome=false testing andna is palindrome=true testing haah is palindrome=true testing habh is palindrome=false testing haaah is palindrome=true
źródło
allMatch
zallMatch(i -> str.charAt(i) == str.charAt(str.length() - i - 1))
?public class Palindromes { public static void main(String[] args) { String word = "reliefpfpfeiller"; char[] warray = word.toCharArray(); System.out.println(isPalindrome(warray)); } public static boolean isPalindrome(char[] word){ if(word.length%2 == 0){ for(int i = 0; i < word.length/2-1; i++){ if(word[i] != word[word.length-i-1]){ return false; } } }else{ for(int i = 0; i < (word.length-1)/2-1; i++){ if(word[i] != word[word.length-i-1]){ return false; } } } return true; } }
źródło
isPalindrome()
z"cbb"
?public class palindrome { public static void main(String[] args) { StringBuffer strBuf1 = new StringBuffer("malayalam"); StringBuffer strBuf2 = new StringBuffer("malayalam"); strBuf2.reverse(); System.out.println(strBuf2); System.out.println((strBuf1.toString()).equals(strBuf2.toString())); if ((strBuf1.toString()).equals(strBuf2.toString())) System.out.println("palindrome"); else System.out.println("not a palindrome"); }
}
źródło
Pracowałem nad rozwiązaniem pytania oznaczonego jako duplikat tego. Równie dobrze mógłbym to tutaj rzucić ...
Pytanie wymagało pojedynczej linii, aby to rozwiązać, i wziąłem to bardziej za literacki palindrom - więc spacje, znaki interpunkcyjne i duże / małe litery mogą zepsuć wynik.
Oto brzydkie rozwiązanie z małą klasą testową:
public class Palindrome { public static boolean isPalendrome(String arg) { return arg.replaceAll("[^A-Za-z]", "").equalsIgnoreCase(new StringBuilder(arg).reverse().toString().replaceAll("[^A-Za-z]", "")); } public static void main(String[] args) { System.out.println(isPalendrome("hiya")); System.out.println(isPalendrome("star buttons not tub rats")); System.out.println(isPalendrome("stab nail at ill Italian bats!")); return; } }
Przepraszam, że to trochę nieprzyjemne - ale inne pytanie dotyczyło tylko jednej linijki.
źródło
Sprawdzając palindrom dla pierwszej połowy ciągu z resztą, ten przypadek zakłada usunięcie wszelkich spacji.
public int isPalindrome(String a) { //Remove all spaces and non alpha characters String ab = a.replaceAll("[^A-Za-z0-9]", "").toLowerCase(); //System.out.println(ab); for (int i=0; i<ab.length()/2; i++) { if(ab.charAt(i) != ab.charAt((ab.length()-1)-i)) { return 0; } } return 1; }
źródło
Jestem nowy w Javie i traktuję Twoje pytanie jako wyzwanie, aby poszerzyć swoją wiedzę.
import java.util.ArrayList; import java.util.List; public class PalindromeRecursiveBoolean { public static boolean isPalindrome(String str) { str = str.toUpperCase(); char[] strChars = str.toCharArray(); List<Character> word = new ArrayList<>(); for (char c : strChars) { word.add(c); } while (true) { if ((word.size() == 1) || (word.size() == 0)) { return true; } if (word.get(0) == word.get(word.size() - 1)) { word.remove(0); word.remove(word.size() - 1); } else { return false; } } } }
źródło
Wypróbuj to:
import java.util.*; public class str { public static void main(String args[]) { Scanner in=new Scanner(System.in); System.out.println("ENTER YOUR STRING: "); String a=in.nextLine(); System.out.println("GIVEN STRING IS: "+a); StringBuffer str=new StringBuffer(a); StringBuffer str2=new StringBuffer(str.reverse()); String s2=new String(str2); System.out.println("THE REVERSED STRING IS: "+str2); if(a.equals(s2)) System.out.println("ITS A PALINDROME"); else System.out.println("ITS NOT A PALINDROME"); } }
źródło
public boolean isPalindrome(String abc){ if(abc != null && abc.length() > 0){ char[] arr = abc.toCharArray(); for (int i = 0; i < arr.length/2; i++) { if(arr[i] != arr[arr.length - 1 - i]){ return false; } } return true; } return false; }
źródło
Innym sposobem jest użycie tablicy char Array
public class Palindrome { public static void main(String[] args) { String str = "madam"; if(isPalindrome(str)) { System.out.println("Palindrome"); } else { System.out.println("Not a Palindrome"); } } private static boolean isPalindrome(String str) { // Convert String to char array char[] charArray = str.toCharArray(); for(int i=0; i < str.length(); i++) { if(charArray[i] != charArray[(str.length()-1) - i]) { return false; } } return true; }
}
źródło
Tutaj moja analiza odpowiedzi @Greg: componentsprogramming.com/palindromes
Uwaga: Ale dla mnie ważne jest, aby zrobić to w sposób ogólny . Wymogi są takie, że sekwencja jest dwukierunkowo iterowalna, a elementy sekwencji są porównywalne przy użyciu równości. Nie wiem, jak to zrobić w Javie, ale tutaj jest wersja C ++, nie znam lepszego sposobu na zrobienie tego dla sekwencji dwukierunkowych.
template <BidirectionalIterator I> requires( EqualityComparable< ValueType<I> > ) bool palindrome( I first, I last ) { I m = middle(first, last); auto rfirst = boost::make_reverse_iterator(last); return std::equal(first, m, rfirst); }
Złożoność: liniowo-czasowa,
Jeśli I to RandomAccessIterator: porównanie podłogi (n / 2) i piętro (n / 2) * 2 iteracje
Jeśli I to DwukierunkowyIterator: podłoga (n / 2) porównania i podłoga (n / 2) * 2 iteracje plus (3/2) * n iteracji w celu znalezienia środka (funkcja środkowa)
przechowywanie: O (1)
Brak pamięci przydzielonej dynamicznie
źródło
Niedawno napisałem program palindromowy, który nie używa StringBuildera. Późna odpowiedź, ale może się to przydać niektórym osobom.
public boolean isPalindrome(String value) { boolean isPalindrome = true; for (int i = 0 , j = value.length() - 1 ; i < j ; i ++ , j --) { if (value.charAt(i) != value.charAt(j)) { isPalindrome = false; } } return isPalindrome; }
źródło
Używając stosu, można to zrobić w ten sposób
import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; import java.util.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); String str=in.nextLine(); str.replaceAll("\\s+",""); //System.out.println(str); Stack<String> stack=new Stack<String>(); stack.push(str); String str_rev=stack.pop(); if(str.equals(str_rev)){ System.out.println("Palindrome"); }else{ System.out.println("Not Palindrome"); } } }
źródło
public static boolean isPalindrome(String word) { String str = ""; for (int i=word.length()-1; i>=0; i--){ str = str + word.charAt(i); } if(str.equalsIgnoreCase(word)){ return true; }else{ return false; } }
źródło
Niesamowite, ile różnych rozwiązań tak prostego problemu istnieje! Oto kolejny.
private static boolean palindrome(String s){ String revS = ""; String checkS = s.toLowerCase(); String[] checkSArr = checkS.split(""); for(String e : checkSArr){ revS = e + revS; } return (checkS.equals(revS)) ? true : false; }
źródło
public static boolean isPalindrome(Object obj) { String s = String.valueOf(obj); for(int left=0, right=s.length()-1; left < right; left++,right--) { if(s.charAt(left++) != s.charAt(right--)) return false; } return true; }
źródło
Dlaczego nie tylko:
boolean isPalindrom(String s) { char[] myChars = s.toCharArray(); for (int i = 0; i < myChars.length/2; i++) { if (myChars[i] != myChars[myChars.length - 1 - i]) { return false; } } return true; }
źródło
import java.util.Scanner; public class Palindrom { public static void main(String []args) { Scanner in = new Scanner(System.in); String str= in.nextLine(); int x= str.length(); if(x%2!=0) { for(int i=0;i<x/2;i++) { if(str.charAt(i)==str.charAt(x-1-i)) { continue; } else { System.out.println("String is not a palindrom"); break; } } } else { for(int i=0;i<=x/2;i++) { if(str.charAt(i)==str.charAt(x-1-i)) { continue; } else { System.out.println("String is not a palindrom"); break; } } } } }
źródło
private static boolean isPalindrome(String word) { int z = word.length(); boolean isPalindrome = false; for (int i = 0; i <= word.length() / 2; i++) { if (word.charAt(i) == word.charAt(--z)) { isPalindrome = true; } } return isPalindrome; }
źródło
Szukałem rozwiązania, które sprawdzało się nie tylko dla palindromów takich jak ...
... ale także dla ...
Iteracyjne : okazało się, że jest to dobre rozwiązanie.
private boolean isPalindromeIterative(final String string) { final char[] characters = string.replaceAll("[\\W]", "").toLowerCase().toCharArray(); int iteratorLeft = 0; int iteratorEnd = characters.length - 1; while (iteratorEnd > iteratorLeft) { if (characters[iteratorLeft++] != characters[iteratorEnd--]) { return false; } } return true; }
Rekurencyjne . Myślę, że to rozwiązanie nie powinno być dużo gorsze niż iteracyjne. To trochę bzdury, które musimy wyodrębnić z metody czyszczenia, aby uniknąć niepotrzebnego przetwarzania.
private boolean isPalindromeRecursive(final String string) { final String cleanString = string.replaceAll("[\\W]", "").toLowerCase(); return isPalindromeRecursiveRecursion(cleanString); } private boolean isPalindromeRecursiveRecursion(final String cleanString) { final int cleanStringLength = cleanString.length(); return cleanStringLength <= 1 || cleanString.charAt(0) == cleanString.charAt(cleanStringLength - 1) && isPalindromeRecursiveRecursion (cleanString.substring(1, cleanStringLength - 1)); }
Cofanie : okazało się, że jest to drogie rozwiązanie.
private boolean isPalindromeReversing(final String string) { final String cleanString = string.replaceAll("[\\W]", "").toLowerCase(); return cleanString.equals(new StringBuilder(cleanString).reverse().toString()); }
Wszystkie podziękowania dla chłopaków, którzy odpowiedzieli w tym poście i rzucili światło na temat.
źródło
Biorąc pod uwagę brak liter w słowach
public static boolean palindromeWords(String s ){ int left=0; int right=s.length()-1; while(left<=right){ while(left<right && !Character.isLetter(s.charAt(left))){ left++; } while(right>0 && !Character.isLetter(s.charAt(right))){ right--; } if((s.charAt(left++))!=(s.charAt(right--))){ return false; } } return true; }
———
@Test public void testPalindromeWords(){ assertTrue(StringExercise.palindromeWords("ece")); assertTrue(StringExercise.palindromeWords("kavak")); assertFalse(StringExercise.palindromeWords("kavakdf")); assertTrue(StringExercise.palindromeWords("akka")); assertTrue(StringExercise.palindromeWords("??e@@c_--e")); }
źródło
Tutaj możesz dynamicznie sprawdzić palindrom liczbę String
import java.util.Scanner; public class Checkpalindrome { public static void main(String args[]) { String original, reverse = ""; Scanner in = new Scanner(System.in); System.out.println("Enter How Many number of Input you want : "); int numOfInt = in.nextInt(); original = in.nextLine(); do { if (numOfInt == 0) { System.out.println("Your Input Conplete"); } else { System.out.println("Enter a string to check palindrome"); original = in.nextLine(); StringBuffer buffer = new StringBuffer(original); reverse = buffer.reverse().toString(); if (original.equalsIgnoreCase(reverse)) { System.out.println("The entered string is Palindrome:"+reverse); } else { System.out.println("The entered string is not Palindrome:"+reverse); } } numOfInt--; } while (numOfInt >= 0); } }
źródło
IMO, rekurencyjny sposób jest najprostszy i najwyraźniejszy.
public static boolean isPal(String s) { if(s.length() == 0 || s.length() == 1) return true; if(s.charAt(0) == s.charAt(s.length()-1)) return isPal(s.substring(1, s.length()-1)); return false; }
źródło
tutaj, sprawdzając największy palindrom w ciągu, zawsze zaczynając od pierwszego znaku.
public static String largestPalindromeInString(String in) { int right = in.length() - 1; int left = 0; char[] word = in.toCharArray(); while (right > left && word[right] != word[left]) { right--; } int lenght = right + 1; while (right > left && word[right] == word[left]) { left++; right--; } if (0 >= right - left) { return new String(Arrays.copyOf(word, lenght )); } else { return largestPalindromeInString( new String(Arrays.copyOf(word, in.length() - 1))); } }
źródło
Fragment kodu:
import java.util.Scanner; class main { public static void main(String []args) { Scanner sc = new Scanner(System.in); String str = sc.next(); String reverse = new StringBuffer(str).reverse().toString(); if(str.equals(reverse)) System.out.println("Pallindrome"); else System.out.println("Not Pallindrome"); } }
źródło