Проверить строку для палиндрома

Палиндром – это слово, фраза, число или другая последовательность единиц, которые можно читать одинаково в любом направлении.

Чтобы проверить, является ли слово палиндром, я получаю массив символов слова и сравниваю символы. Я тестировал его и, похоже, работал. Однако я хочу знать, правильно ли это или что-то улучшить.

Вот мой код:

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; } } 

Почему не просто:

 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; } 

Пример:

Вход – «andna».
i1 будет 0, а i2 – 4.

Итерацию первого цикла будем сравнивать word[0] и word[4] . Они равны, поэтому мы увеличиваем i1 (теперь 1) и уменьшаем i2 (теперь 3).
Поэтому мы сравниваем n. Они равны, поэтому мы увеличиваем i1 (сейчас 2) и уменьшаем i2 (это 2).
Теперь i1 и i2 равны (они оба равны 2), поэтому условие для цикла while больше не является истинным, поэтому цикл завершается, и мы возвращаем true.

Вы можете проверить, является ли строка палиндром, сравнивая ее с обратным:

 public static boolean isPalindrome(String str) { return str.equals(new StringBuilder(str).reverse().toString()); } 

или для версий Java раньше 1.5,

 public static boolean isPalindrome(String str) { return str.equals(new StringBuffer().append(str).reverse().toString()); } 

EDIT: @FernandoPelliccioni предоставил очень тщательный анализ эффективности (или отсутствия) этого решения, как с точки зрения времени, так и пространства. Если вас интересует вычислительная сложность этого и других возможных решений этого вопроса, прочитайте его!

Краткая версия, которая не включает (неэффективно) инициализацию связки объектов:

 boolean isPalindrome(String str) { int n = str.length(); for( int i = 0; i < n/2; i++ ) if (str.charAt(i) != str.charAt(ni-1)) return false; return true; } 

Альтернативно, recursion .

Для тех, кто ищет более короткое рекурсивное решение, чтобы проверить, удовлетворяет ли данная строка палиндром:

 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)); } } 

ИЛИ даже короче , если хотите:

 private boolean isPalindrome(String s) { int length = s.length(); if (length < 2) return true; else return s.charAt(0) != s.charAt(length - 1) ? false : isPalindrome(s.substring(1, length - 1)); } 

Go, 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 

также другое перспективное решение:

 public static boolean isPalindrome(String s) { for (int i=0 , j=s.length()-1 ; i 
 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){ 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{ for(int i = 0; i < (wort.length-1)/2-1; i++){ if(wort[i] != wort[wort.length-i-1]){ return false; } } } return true; } } 

И вот полное streamовое решение Java 8. IntStream предоставляет все индексы с половиной длины строк, а затем выполняется сравнение с начала и с конца.

 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)); } 

Выход:

 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 

Проверка палиндрома для первой половины строки с остальным, этот случай предполагает удаление любых пробелов.

 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 
 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"); } 

}

Я работал над решением вопроса, который был отмечен как дубликат этого. Можете также бросить его здесь …

Вопрос попросил одну строку, чтобы решить эту проблему, и я воспринял ее как литературный палиндром – поэтому пробелы, пунктуация и верхний / нижний регистр могут отбросить результат.

Вот уродливое решение с небольшим тестовым classом:

 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; } } 

Извините, что это отвратительно, но другой вопрос задал однострочный.

Удивительно, сколько существует различных решений такой простой проблемы! Вот еще один.

 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; } 

Попробуйте это:

 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"); } } 

Я новичок в java, и я рассматриваю ваш вопрос как задачу улучшить свои знания.

 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 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; } } } } 
  1. Если строка состоит из букв или одной буквы, это палиндром.
  2. В противном случае сравните первую и последнюю буквы строки.
    • Если первая и последняя буквы отличаются, то строка не является палиндром
    • В противном случае первая и последняя буквы одинаковы. Разделите их из строки и определите, является ли оставшаяся строка палиндром. Возьмите ответ за эту меньшую строку и используйте ее в качестве ответа для исходной строки, затем повторите с 1 .
 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; } 

Другой способ – использовать 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; } 

}

Здесь мой анализ ответа @Greg: componentsprogramming.com/palindromes


Sidenote: Но для меня важно сделать это общим способом . Требования заключаются в том, что последовательность является двунаправленной итерацией, а элементы последовательности – сравнимыми с использованием равенства. Я не знаю, как это сделать в Java, но, вот версия C ++, я не знаю, как лучше это сделать для двунаправленных последовательностей.

 template  requires( EqualityComparable< ValueType > ) bool palindrome( I first, I last ) { I m = middle(first, last); auto rfirst = boost::make_reverse_iterator(last); return std::equal(first, m, rfirst); } 

Сложность: линейное время,

  • Если я RandomAccessIterator: пол (n / 2) сравнения и пол (n / 2) * 2 итерации

  • Если я двунаправленныйИтератор: пол (n / 2) сравнения и пол (n / 2) * 2 итерации плюс (3/2) * n итераций, чтобы найти среднюю (среднюю функцию)

  • хранение: O (1)

  • Нет динамической выделенной памяти


Недавно я написал программу палиндрома, которая не использует StringBuilder. Поздний ответ, но это может пригодиться некоторым людям.

 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; } 

Используя стек, это можно сделать так:

 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 stack=new Stack(); stack.push(str); String str_rev=stack.pop(); if(str.equals(str_rev)){ System.out.println("Palindrome"); }else{ System.out.println("Not Palindrome"); } } } 
  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; } } 
 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 
 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; } 

Я искал решение, которое не только работало для палиндромов, как …

  • “Kayak”
  • “Госпожа”

… но и для …

  • «Человек, план, канал, Панама!»
  • «Это была машина или кошка, которую я видел?»
  • «Нет« х »в Никсоне»

Итеративный : это было доказано как хорошее решение.

 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; } 

Рекурсивный . Я думаю, что это решение не должно быть намного хуже, чем итеративный. Нам нужна небольшая терапия, чтобы извлечь очищающий шаг из метода, чтобы избежать ненужного процесса.

 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)); } 

Реверсирование : это было доказано как дорогостоящее решение.

 private boolean isPalindromeReversing(final String string) { final String cleanString = string.replaceAll("[\\W]", "").toLowerCase(); return cleanString.equals(new StringBuilder(cleanString).reverse().toString()); } 

Все кредиты ребятам, которые отвечают на этот пост и привносят свет в эту тему.

Принимая во внимание не буквы в словах

 public static boolean palindromeWords(String s ){ int left=0; int right=s.length()-1; while(left<=right){ while(left0 && !Character.isLetter(s.charAt(right))){ right--; } if((s.charAt(left++))!=(s.charAt(right--))){ return false; } } return true; } в public static boolean palindromeWords(String s ){ int left=0; int right=s.length()-1; while(left<=right){ while(left0 && !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("[email protected]@c_--e")); } 

Здесь вы можете проверить палиндром на число строк динамически

 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); } } 

ИМО, рекурсивный путь является самым простым и ясным.

 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; } 

здесь, проверяя самый большой палиндром в строке, всегда начиная с 1-го символа.

 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))); } } 

Фрагмент кода:

 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"); } } 

введите описание изображения здесь

 import java.util.Collections; import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class GetAllPalindromes { static Scanner in; public static void main(String[] args) { in = new Scanner(System.in); System.out.println("Enter a string \n"); String abc = in.nextLine(); Set a = printAllPalindromes(abc); System.out.println("set is " + a); } public static Set printAllPalindromes(String input) { if (input.length() <= 2) { return Collections.emptySet(); } Set out = new HashSet(); int length = input.length(); for (int i = 1; i < length - 1; i++) { for (int j = i - 1, k = i + 1; j >= 0 && k < length; j--, k++) { if (input.charAt(j) == input.charAt(k)) { out.add(input.subSequence(j, k + 1)); } else { break; } } } return out; } } **Get All Palindrome in s given string** 

Выход D: \ Java> java GetAllPalindromes Введите строку

Привет, пользователь nitin, мой лучший друг!

Ответ задан как [nitin, nitin, wow, wow, iti]

D: \ Java>

For-loop содержит sub.length() / 2 - 1 . Он должен быть вычтен с помощью 1, поскольку элемент в середине строки не должен проверяться.

Например, если нам нужно проверить строку с 7 символами (1234567), то 7/2 => 3, а затем мы вычитаем 1, и поэтому позиции в строке станут (0123456). Символы, проверенные с помощью элемента 0, 1, 2 с 6, 5, 4 соответственно. Мы не заботимся о элементе в позиции 3, поскольку он находится в точной середине строки.

  private boolean isPalindromic(String sub) { for (int i = 0; i <= sub.length() / 2 - 1; i++) { if (sub.charAt(i) != sub.charAt(sub.length() - 1 - i)) { return false; } } return true; } 
  • Как распечатать уникальные элементы в массиве Perl?
  • Получение размера malloc только с возвращенным указателем
  • Как сделать глубокую копию массива 2d в Java?
  • Инициализация массива PowerShell
  • Передача массивов в качестве параметров в bash
  • Преобразование массива символов C в строку
  • Заменить форму массива таблиц с массивом памяти VBA
  • Как resize многомерного (2D) массива в C #?
  • C ++ int в байтовый массив
  • Как преобразовать ArrayList, содержащий целые числа в примитивный массив int?
  • [Обозначение массива L - откуда оно взялось?
  • Давайте будем гением компьютера.