检查回文字符串

回文是一个单词、短语、数字或其他单位序列，它们可以在任一方向上以相同的方式读取。

为了检查一个单词是否是回文，我得到该单词的字符数组并比较这些字符。我测试过了，似乎有效。但是我想知道这是否正确，或者是否有什么需要改进的地方。

这是我的代码:

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;
}
}
371036 次浏览
小开
最佳答案

Why not just:

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

Example:

Input is "andna".
i1 will be 0 and i2 will be 4.

First loop iteration we will compare word[0] and word[4]. They're equal, so we increment i1 (it's now 1) and decrement i2 (it's now 3).
So we then compare the n's. They're equal, so we increment i1 (it's now 2) and decrement i2 (it's 2).
Now i1 and i2 are equal (they're both 2), so the condition for the while loop is no longer true so the loop terminates and we return 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;
}
}
小开

You can check if a string is a palindrome by comparing it to the reverse of itself:

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

or for versions of Java earlier than 1.5,

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

EDIT: @FernandoPelliccioni provided a very thorough analysis of the efficiency (or lack thereof) of this solution, both in terms of time and space. If you're interested in the computational complexity of this and other possible solutions to this question, please read it!

小开

I worked on a solution for a question that was marked as duplicate of this one. Might as well throw it here...

The question requested a single line to solve this, and I took it more as the literary palindrome - so spaces, punctuation and upper/lower case can throw off the result.

Here's the ugly solution with a small test 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;
}
}

Sorry that it is kind of nasty - but the other question specified a one-liner.

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

}

小开

A concise version, that doesn't involve (inefficiently) initializing a bunch of objects:

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

Try this out :

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

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
小开

I'm new to java and I'm taking up your question as a challenge to improve my knowledge.

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. If the string is made of no letters or just one letter, it is a palindrome.
  2. Otherwise, compare the first and last letters of the string.
    • If the first and last letters differ, then the string is not a palindrome
    • Otherwise, the first and last letters are the same. Strip them from the string, and determine whether the string that remains is a palindrome. Take the answer for this smaller string and use it as the answer for the original string then repeat from 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;
}
小开

Another way is using 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;
}

}

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


}
}
}


}
小开

also a different looking solution:

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

I was looking for a solution that not only worked for palindromes like...

  • "Kayak"
  • "Madam"

...but as well for...

  • "A man, a plan, a canal, Panama!"
  • "Was it a car or a cat I saw?"
  • "No 'x' in Nixon"

Iterative: This has be proven as a good solution.

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

Recursive. I think this solution shouldn't be much worse than the iterative one. Is a little bit crapy we need to extract the cleaning step out of the method to avoid unnecesary procesing.

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

Reversing: This has been proved as a expensive solution.

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

All the credits to the guys answering in this post and bringing light to the topic.

小开

Alternatively, recursion.

For anybody who is looking for a shorter recursive solution, to check if a given string satisfies as a palindrome:

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

OR even shorter, if you'd like:

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

Here my analysis of the @Greg answer: componentsprogramming.com/palindromes

Sidenote: But, for me it is important to do it in a Generic way. The requirements are that the sequence is bidirectionally iterable and the elements of the sequence are comparables using equality. I don't know how to do it in Java, but, here is a C++ version, I don't know a better way to do it for bidirectional sequences.

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

Complexity: linear-time,

  • If I is RandomAccessIterator: floor(n/2) comparissons and floor(n/2)*2 iterations

  • If I is BidirectionalIterator: floor(n/2) comparissons and floor(n/2)*2 iterations plus (3/2)*n iterations to find the middle ( middle function )

  • storage: O(1)

  • No dymamic allocated memory

小开

Considering not letters in the words

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

Here you can check palindrome a number of String dynamically

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

IMO, the recursive way is the simplest and clearest.

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

here, checking for the largest palindrome in a string, always starting from 1st char.

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

Code Snippet:

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

Recently I wrote a palindrome program which doesn't use StringBuilder. A late answer but this might come in handy to some people.

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

Using stack, it can be done like this

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

And here a complete Java 8 streaming solution. An IntStream provides all indexes til strings half length and then a comparision from the start and from the end is done.

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

Output is:

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


}
小开

Checking palindrome for first half of the string with the rest, this case assumes removal of any white spaces.

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

enter image description here

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<CharSequence> printAllPalindromes(String input)
{
if (input.length() <= 2) {
return Collections.emptySet();
}


Set<CharSequence> out = new HashSet<CharSequence>();
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**

Output D:\Java>java GetAllPalindromes Enter a string

Hello user nitin is my best friend wow !

Answer is set is [nitin, nitin , wow , wow, iti]

D:\Java>

小开

For-loop contains sub.length() / 2 - 1 . It has to be subtracted with 1 as the element in the middle of the string does not have to checked.

For example, if we have to check an string with 7 chars (1234567), then 7/2 => 3 and then we subtrack 1, and so the positions in the string will become (0123456). The chars checked with be the 0, 1, 2 element with the 6, 5, 4 respectively. We do not care about the element at the position 3 as it is in the exact middle of the string. 

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

Amazing how many different solutions to such a simple problem exist! Here's another one. 

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;
}
小开 
 public boolean isPalindrome(String input) {
char[] inputChars = input.toCharArray();
int inputLength = inputChars.length;
int inputMid = inputLength / 2;


for (int i = 0; i <= inputMid; i++) {
if (inputChars[i] != inputChars[inputLength - i - 1]) {
return false;
}
}
return true;
}

The method determines whether a string input is a palindrome. In this method the loop iterates for half of the input length resulting in less performance concern and more concise application.

小开 
import java.io.*;
import 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");
}
}
小开
  • This implementation works for numbers and strings.
  • Since we are not writing anything, so there is no need to convert the string into the character array.
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;
}
小开

In PHP

function isPalindrome($string) {
return (strrev($string) == $string) ? true : false;
}


var_dump(isPalindrome('madam')); //bool(true)
var_dump(isPalindrome('dell')); //bool(false)
var_dump(isPalindrome('1221')); //bool(true)
小开 
/**
* Check whether a word is a palindrome
*
* @param word the word
* @param low  low index
* @param high high index
* @return {@code true} if the word is a palindrome;
* {@code false} otherwise
*/
private static boolean isPalindrome(char[] word, int low, int high) {
if (low >= high) {
return true;
} else if (word[low] != word[high]) {
return false;
} else {
return isPalindrome(word, low + 1, high - 1);
}
}


/**
* Check whether a word is a palindrome
*
* @param the word
* @return {@code true} if the word is a palindrome;
* @code false} otherwise
*/
private static boolean isPalindrome(char[] word) {
int length = word.length;
for (int i = 0; i <= length / 2; i++) {
if (word[i] != word[length - 1 - i]) {
return false;
}
}
return true;
}


public static void main(String[] args) {
char[] word = {'a', 'b', 'c', 'b', 'a' };
System.out.println(isPalindrome(word, 0, word.length - 1));
System.out.println(isPalindrome(word));
}
小开

Using 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]);
}
小开

Why not just : 

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;
}
小开 
public class palindrome {


public static void main(String[] args) {


Scanner scanner=new Scanner(System.in);
System.out.println("Enter the line you want to check palindrome:");
String s= scanner.nextLine();


StringTokenizer separate = new StringTokenizer(s, " ");
System.out.println("\nPalindrome Words are: ");
while(separate.hasMoreTokens()) {
String word = separate.nextToken();
String reversedWord = new StringBuilder(word).reverse().toString().toLowerCase();
if ((word.toLowerCase().equals(reversedWord))){
System.out.println(word);
}
}
}
}
小开

We can reduce the loop to half of the length:

function isPallindrome(s) {
let word= s.toLowerCase();
let length = word.length -1;
let isPallindrome= true;
for(let i=0; i< length/2 ;i++){
if(word[i] !== word[length -i]){
isPallindrome= false;
break;
}
}
return isPallindrome;
}
小开

I created a new time complexitey Java solution 7 ms, and very easy! I take the desired numbers and letters from the ASCII table, do not touch the rest, and finally return true or false, checking that the two strings are equal to each other.

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());
小开

Besides the way using StringBuilder/StringBuffer to reverse the string and check it still equals the original one, here's a way by for loop.

private boolean isPalindrome(String word) {
if (word == null || word.isEmpty()) {
return false;
}


int length = word.length();
int middleIndex = length / 2;


for (int index = 0; index < middleIndex; index++) {
if (word.charAt(index) != word.charAt(length - index - 1)) {
return false;
}
}


return true;
}

提交答案