Проверьте строку на палиндром
Палиндром - это слово, фраза, число или другая последовательность единиц, которые могут быть прочитаны одинаково в любом направлении.
Чтобы проверить, является ли слово палиндромом, я получаю массив символов слова и сравниваю символы. Я проверил это, и это похоже на работу. Однако я хочу знать, правильно ли это или есть что-то, что можно улучшить.
Вот мой код:
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;
}
}
43 ответа
Почему не просто
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;
}
Пример:
Ввод "андна".
i1 будет 0, а i2 будет 4.
Первый цикл итерации сравним word[0] а также word[4], Они равны, поэтому мы увеличиваем i1 (теперь 1) и уменьшаем i2 (теперь 3).
Итак, мы затем сравним н. Они равны, поэтому мы увеличиваем 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());
}
РЕДАКТИРОВАТЬ: @FernandoPelliccioni предоставил очень тщательный анализ эффективности (или его отсутствия) этого решения, как с точки зрения времени и пространства. Если вы заинтересованы в вычислительной сложности этого и других возможных решений этого вопроса, пожалуйста, прочтите его!
Краткая версия, которая не включает (неэффективно) инициализацию группы объектов:
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;
}
Как вариант, рекурсия.
Для любого, кто ищет более короткое рекурсивное решение, проверить, удовлетворяет ли данная строка как палиндром:
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<j ; i++ , j-- ) {
if ( s.charAt(i) != s.charAt(j) ) {
return false;
}
}
return true;
}
И вот полное потоковое решение 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 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;
}
}
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");
}
}
Я работал над решением вопроса, который был помечен как дубликат этого. Можешь бросить это сюда...
Вопрос требовал единственной строки, чтобы решить эту проблему, и я воспринял это больше как литературный палиндром - так что пробелы, знаки препинания и прописные / строчные буквы могут отбрасывать результат.
Вот уродливое решение с небольшим тестовым классом:
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;
}
}
Извините, что это противно - но другой вопрос указывал на одну строку.
Проверка палиндрома на первую половину строки с остальными, этот случай предполагает удаление любых пробелов.
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;
}
Удивительно, сколько существует разных решений такой простой проблемы! Вот еще один.
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;
}
Я новичок в 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<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;
}
}
}
}
- Если строка состоит из букв или только одной буквы, это палиндром.
- В противном случае сравните первую и последнюю буквы строки.
- Если первая и последняя буквы различаются, то строка не является палиндромом
- В противном случае первая и последняя буквы совпадают. Уберите их из строки и определите, является ли оставшаяся строка палиндромом. Возьмите ответ для этой меньшей строки и используйте его в качестве ответа для исходной строки, затем повторите процедуру с 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;
}
}
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.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");
}
}
}
Попробуйте это:
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");
}
}
Почему не просто:
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;
}
Вот мой анализ ответа @Greg: http://componentsprogramming.com/palindromes
Sidenote: Но для меня важно сделать это в общем виде. Требования состоят в том, чтобы последовательность была двунаправленной итерацией, а элементы последовательности сравнимы с использованием равенства. Я не знаю, как это сделать в Java, но вот версия на C++, я не знаю лучшего способа сделать это для двунаправленных последовательностей.
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);
}
Сложность: линейно-временная,
Если I - RandomAccessIterator: минимальное (n/2) сравнение и минимальное (n/2)*2 итерации
Если I - BidirectionalIterator: нижние (n/2) сравнения и нижние (n/2)*2 итерации плюс (3/2)*n итераций для поиска середины (средняя функция)
хранение: O(1)
Нет памяти выделенной памяти
- Эта реализация работает для чисел и строк.
- Поскольку мы ничего не пишем, нет необходимости преобразовывать строку в массив символов.
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;
}
Недавно я написал программу для палиндрома, которая не использует 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;
}
Я создал новое сложное Java-решение за 7 мсек, и это очень просто! Я беру нужные числа и буквы из таблицы ASCII, не трогаю остальные и, наконец, возвращаю истину или ложь, проверяя, что две строки равны друг другу.
StringBuilder newString = new StringBuilder();
s = s.toLowerCase();
for (char ch : s.toCharArray()) {
if (97 <= (int) ch && (int) ch <= 122 || 48 <= (int)ch && (int)ch <= 57) {
newString.append(ch);
}
}
String nextS = new StringBuilder(newString).reverse().toString();
return nextS.equals(newString.toString());
Здесь проверяется самый большой палиндром в строке, всегда начиная с 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)));
}
}
package basicprogm;
public class pallindrome {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s= "madam" ;
//to store the values that we got in loop
String t="";
for(int i=s.length()-1;i>=0;i--){
t=t+s.charAt(i);
}
System.out.println("reversed word is "+ t);
if (t.matches(s)){
System.out.println("pallindrome");
}
else{
System.out.println("not pallindrome");
}
}
}
Фрагмент кода:
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");
}
}
Импорт java.io. ; импорт java.util.;
Public Class Solution {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String A=sc.next();
char[] array = A.toCharArray();
String str = "";
for(int i=A.length()-1;i>=0;i--){
str = str + array[i];
}
if(A.equalsIgnoreCase(str))System.out.println("Yes");
else System.out.println("No");
}}
Учитывая не буквы в словах
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"));
}
Палиндром с рекурсией (JavaScript)
var isPalindrome = function(str) {
if(str.length <=1) return true;
if (str[0] !== str[str.length-1]) return false;
return isPalindrome(str.slice(1,-1));
}
isPalindrome(aba)
Использование Stream API:
private static boolean isPalindrome(char[] warray) {
return IntStream.range(0, warray.length - 1)
.takeWhile(i -> i < warray.length / 2)
.noneMatch(i -> warray[i] != warray[warray.length - 1 - i]);
}