views:

13143

answers:

60

Definition:

A palindrome is a word, phrase, number or other sequence of units that has the property of reading the same in either direction

How to check if the given string is a palindrome?

This was one of the FAIQ [Frequently Asked Interview Question] a while ago but that mostly using C.

Looking for solutions in any and all languages possible.

+2  A: 
boolean isPalindrome(String str1) {
  //first strip out punctuation and spaces
  String stripped = str1.replaceAll("[^a-zA-Z0-9]", "");
  return stripped.equalsIgnoreCase((new StringBuilder(stripped)).reverse().toString());
}

Java version

Ryan Ahearn
Striktly I would not allow IgnoreCase for a palindrome.
Ralph Rickenbach
Why not? See http://www.merriam-webster.com/dictionary/palindrome
xanadont
Why not? If case matters then "A man a plan a canal Panama" isn't a palindrome.
Ryan Ahearn
Who says "A man a plan a canal Panama" is a palindrome? In my opinion, this does not read the same as "amanap lanac a nalp a nam a"
Fortega
+30  A: 

Language agnostic meta-code then...

rev = StringReverse(originalString)
return ( rev == originalString );
Tnilsson
ha ha. very smart :)
Prakash
Solutions like these are great because they are easy to follow. The solutions with loops, stacks, etc. are nice but harder to inspect than this one.All this needs is a line or two to trim it down to a fixed alphabet (just [a-zA-Z] characters?).
Michael Haren
You'd have to remove the spaces from the string first, otherwise palindrome's like "a man a plan a canal panama" wouldn't check properly.
Justin Bennett
In whatever language that is, why not just do "return StringReverse(originalString)==originalString"
rjmunro
don't forget that one usually want's an case-insensitive string comparison!
bene
it doesn't check if the palindrome is words, like "no means no".
Shabbyrobe
I'm surprised this one is voted up so much considering it's wrong. As people have pointed out, it will not work for all palindromes, specifically with punctuation etc. The wisdom of crowds eh..
SCdF
With a strict definition of a palindrome, however, this works exactly. The definition does not specify what "reading the same in either direction" means, and as such, a strict character for character comparison, which this is, is the most simple algorithm.
cdeszaq
Why do you use `if (a == b) return true else return false` instead of just `return a == b`? IMHO it is a horrible practice.
J.F. Sebastian
Fixed - yay for community wiki posts, eh.
Blorgbeard
@SCdF with the new feature of upvoting comments, I upvoted yours, thus mitigating a bit the damage of a wrong solution being the most voted one.
Daniel Daranas
+2  A: 

Here's my solution in c#

static bool isPalindrome(string s)
{
 string allowedChars = "abcdefghijklmnopqrstuvwxyz"+
        "1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 string compareString = String.Empty;
 string rev = string.Empty;

 for (int i = 0; i <= s.Length - 1; i++)
 {
  char c = s[i];

  if (allowedChars.IndexOf(c) > -1)
  {
   compareString += c;
  }
 }


 for (int i = compareString.Length - 1; i >= 0; i--)
 {
     char c = compareString[i];
     rev += c;
 }

 return rev.Equals(compareString, 
        StringComparison.CurrentCultureIgnoreCase);
}
Jared
+4  A: 
Delphi

function IsPalindrome(const s: string): boolean;
var
  i, j: integer;
begin
  Result := false;
  j := Length(s);
  for i := 1 to Length(s) div 2 do begin
    if s[i] <> s[j] then
      Exit;
    Dec(j);
  end;
  Result := true;
end;
gabr
+11  A: 

Unoptimized Python:

>>> def is_palindrome(s):
...     return s == s[::-1]
Blair Conrad
I try. I often fail, but not this time, it would seem. Thanks.
Blair Conrad
I was going to suggest that you could edit your answer to add in the whitespace and punctuation handling from my answer below but then it wouldn't be so pretty. :-)
Dave Webb
A one line function like that can be done as a lambda:is_palindrome=lambda s:s == s[::-1]
rjmunro
Why make a function at all, when you can just do "is_palindrome = s == s[::-1]"? ;)
Anders Sandvig
Anders Sandvig: for readability? And perhaps ease of maintenance in case we decide to ignore whitespace and punctuation as Dave Webb has done?
Blair Conrad
It doesn't work for sequences that doesn't support extended slicing. http://www.python.org/doc/2.5.2/ref/slicings.html . But `def ispal(iterable): s = list(iterable); return s == s[::-1]` does work.
J.F. Sebastian
+8  A: 

Remember, you'll want to strip out punctuation characters - spaces, commas, exclamation points, etc. - before processing.

ceejayoz
Do you? the question isn't stated as such. Should "a man, a plan, a canal, panama" be a palindrome, or just "amanaplanacanalpanama"? Definitely changes some of these answers.
Baltimark
According to Wikipedia, "the adjustment of punctuation and spaces between words is generally permitted". Very few phrases qualify if you don't permit it.
ceejayoz
+6  A: 

Here's a python way. Note: this isn't really that "pythonic" but it demonstrates the algorithm.

def IsPalindromeString(n):
    myLen = len(n)
    i = 0
    while i <= myLen/2:
        if n[i] != n[myLen-1-i]:
            return False
        i += 1
    return True
Baltimark
If you don't like: `ispalindrome = lamdba s: s == s[::-1]` then you could use `def ispalindrome(seq): return all(seq[i] == seq[-i-1] for i in range(len(seq) // 2))`
J.F. Sebastian
btw, CamelCase is not recommended for function and local variable names. See 'Style Guide for Python Code' http://www.python.org/dev/peps/pep-0008/
J.F. Sebastian
+26  A: 

Windows XP (might also work on 2000) or later BATCH script:

@echo off

call :is_palindrome %1
if %ERRORLEVEL% == 0 (
    echo %1 is a palindrome
) else (
    echo %1 is NOT a palindrome
)
exit /B 0

:is_palindrome
    set word=%~1
    set reverse=
    call :reverse_chars "%word%"
    set return=1
    if "$%word%" == "$%reverse%" (
        set return=0
    )
exit /B %return%

:reverse_chars
    set chars=%~1
    set reverse=%chars:~0,1%%reverse%
    set chars=%chars:~1%
    if "$%chars%" == "$" (
        exit /B 0
    ) else (
        call :reverse_chars "%chars%"
    )
exit /B 0
Paulius Maruška
Awesome, batch FTW!
Simon Steele
+1 because you used a batch script... badass.
Daniel Schaffer
Seriously, that's awesome. +1
unforgiven3
+12  A: 

C#: LINQ

var str = "a b a";
var test = Enumerable.SequenceEqual(str.ToCharArray(), 
           str.ToCharArray().Reverse());
aku
+1  A: 

Many ways to do it. I guess the key is to do it in the most efficient way possible (without looping the string). I would do it as a char array which can be reversed easily (using C#).

string mystring = "abracadabra";

char[] str = mystring.ToCharArray();
Array.Reverse(str);
string revstring = new string(str);

if (mystring.equals(revstring))
{
    Console.WriteLine("String is a Palindrome");
}
Ryan Farley
+11  A: 

C# in-place algorithm. Any preprocessing, like case insensitivity or stripping of whitespace and punctuation should be done before passing to this function.

boolean IsPalindrome(string s) {
    for (int i = 0; i < s.Length / 2; i++)
    {
        if (s[i] != s[s.Length - 1 - i]) return false;
    }
    return true;
}


Edit: removed unnecessary "+1" in loop condition and spent the saved comparison on removing the redundant Length comparison. Thanks to the commenters!

David Schmitt
I think you have a benign fencepost error there.
Imbue
I think you need to be a little bit more specific there.
David Schmitt
Sorry, I'm talking about the s.Length / 2 + 1. It looks like the plus one will only ever make you check the middle letter in an odd length word, or the middle two letters in an even length word twice.
Imbue
I've agreed with Imbue. Consider s = 'aba': s.Length / 2 == 1 -> i<=1 -> s[1] = s[3 - 1 - 1] (unnecessary comparison of middle letter with itself) or s = 'ab': s.Length / 2 == 1 -> i <= 1 -> s[1] = s[2 - 1 - 1] (letters checked twice unnecessary).
J.F. Sebastian
Additionally It is unclear whether an empty string is a palindrome.
J.F. Sebastian
re fencepost: d'oh, you're right of course! re empty string: `"".reverse() == ""`, so I'm quite sure that the empty string is a palindrome, as is every one-character string.
David Schmitt
The `if (s.Length < 2)` is redundant. s.Length /2 == 0 if s.Length < 2 therefore i < 0 == false -> return true.
J.F. Sebastian
+4  A: 

Using a good data structure usually helps impress the professor:

Push half the chars onto a stack (Length / 2).
Pop and compare each char until the first unmatch.
If the stack has zero elements: palindrome.
*in the case of a string with an odd Length, throw out the middle char.

xanadont
Using O(n) memory where a in-place algorithm works would probably not impress a professor
David Schmitt
*Assume a 101 course. ;)
xanadont
+3  A: 

Here's my solution, without using a strrev. Written in C#, but it will work in any language that has a string length function.

private static bool Pal(string s) {
 for (int i = 0; i < s.Length; i++) {
  if (s[i] != s[s.Length - 1 - i]) {
   return false;
  }
 }
 return true;
}
swilliams
replace `i < s.Length` by `i < s.Length / 2`
J.F. Sebastian
Doesn't work because it doesn't ignore whitespace or punctuation.
John Dibling
it will work in any language that has a string length function. -> that's not really true. s[i] does not compile in java :)
Fortega
+2  A: 

This Java code should work inside a boolean method:

Note: You only need to check the first half of the characters with the back half, otherwise you are overlapping and doubling the amount of checks that need to be made.

private static boolean doPal(String test) {
    for(int i = 0; i < test.length() / 2; i++) {
        if(test.charAt(i) != test.charAt(test.length() - 1 - i)) {
            return false;
        }
    }
    return true;
}
Kamikaze Mercenary
+4  A: 

Java solution:

public class QuickTest {

public static void main(String[] args) {
    check("AmanaplanacanalPanama".toLowerCase());
    check("Hello World".toLowerCase());
}

public static void check(String aString) {
    System.out.print(aString + ": ");
    char[] chars = aString.toCharArray();
    for (int i = 0, j = (chars.length - 1); i < (chars.length / 2); i++, j--) {
        if (chars[i] != chars[j]) {
            System.out.println("Not a palindrome!");
            return;
        }
    }
    System.out.println("Found a palindrome!");
}

}

Jonathan
+37  A: 

PHP sample:

$string = "A man, a plan, a canal, Panama";

function is_palindrome($string)
{
    $a = strtolower(preg_replace("/[^A-Za-z0-9]/","",$string));
    return $a==strrev($a);
}

Removes any non-alphanumeric characters (spaces, commas, exclamation points, etc.) to allow for full sentences as above, as well as simple words.

ConroyP
It doesn't work for numbers and languages other then English.
J.F. Sebastian
Just curious - why not strtolower() first so you have a shorter regex?
Chris Lutz
+2  A: 

EDIT: from the comments:

bool palindrome(std::string const& s) 
{ 
  return std::equal(s.begin(), s.end(), s.rbegin()); 
}


The c++ way.

My naive implementation using the elegant iterators. In reality, you would probably check and stop once your forward iterator has past the halfway mark to your string.

#include <string>
#include <iostream>

using namespace std;
bool palindrome(string foo)
{
    string::iterator front;
    string::reverse_iterator back;
    bool is_palindrome = true;
    for(front = foo.begin(), back = foo.rbegin();
        is_palindrome && front!= foo.end() && back != foo.rend();
        ++front, ++back
        )
    {
        if(*front != *back)
            is_palindrome = false;
    }
    return is_palindrome;
}
int main()
{
    string a = "hi there", b = "laval";

    cout << "String a: \"" << a << "\" is " << ((palindrome(a))? "" : "not ") << "a palindrome." <<endl;
    cout << "String b: \"" << b << "\" is " << ((palindrome(b))? "" : "not ") << "a palindrome." <<endl;

}
Flame
Or perhaps:bool palindrome(string foo){ return std::equal(foo.begin(), foo.end(), foo.rbegin());}
Daniel James
Oh, and string should be passed as a reference: bool palindrome(string const }
Daniel James
I like that, much more elegant.
Flame
A: 

Another one from Delphi, which I think is a little more rigorous than the other Delphi example submitted. This can easily turn into a golfing match, but I've tried to make mine readable.

Edit0: I was curious about the performance characteristics, so I did a little test. On my machine, I ran this function against a 60 character string 50 million times, and it took 5 seconds.

function TForm1.IsPalindrome(txt: string): boolean;
var
  i, halfway, len : integer;
begin
  Result := True;
  len := Length(txt);

  {
  special cases:
  an empty string is *never* a palindrome
  a 1-character string is *always* a palindrome
  }
  case len of
    0 : Result := False;
    1 : Result := True;
    else begin
      halfway := Round((len/2) - (1/2));  //if odd, round down to get 1/2way pt

      //scan half of our string, make sure it is mirrored on the other half
      for i := 1 to halfway do begin
        if txt[i] <> txt[len-(i-1)] then begin
          Result := False;
          Break;
        end;  //if we found a non-mirrored character
      end;  //for 1st half of string
    end;  //else not a special case
  end;  //case
end;

And here is the same thing, in C#, except that I've left it with multiple exit points, which I don't like.

private bool IsPalindrome(string txt) {
  int len = txt.Length;

  /*
  Special cases:
  An empty string is *never* a palindrome
  A 1-character string is *always* a palindrome
  */    
  switch (len) {
    case 0: return false;
    case 1: return true;
  }  //switch
  int halfway = (len / 2);

  //scan half of our string, make sure it is mirrored on the other half
  for (int i = 0; i < halfway; ++i) {
    if (txt.Substring(i,1) != txt.Substring(len - i - 1,1)) {
      return false;
    }  //if
  }  //for
  return true;
}
JosephStyons
The only difference is that my code treats empty string as a palindrome. That is by design.
gabr
A: 

C#3 - This returns false as soon as a char counted from the beginning fails to match its equivalent at the end:

static bool IsPalindrome(this string input)
{
    char[] letters = input.ToUpper().ToCharArray();

    int i = 0;
    while( i < letters.Length / 2 )
        if( letters[i] != letters[letters.Length - ++i] )
            return false;

    return true;
}
Keith
Is there an off-by-one error here? The first comparison is between letters[0] and letters[letters.Length-0], shouldn't the latter be letter[letters.Length-1]?
Eric
Thanks, well spotted. Example changed.
Keith
+2  A: 

Here's a Python version that deals with different cases, punctuation and whitespace.

import string

def is_palindrome(palindrome):
    letters = palindrome.translate(string.maketrans("",""),
                  string.whitespace + string.punctuation).lower()
    return letters == letters[::-1]

Edit: Shamelessly stole from Blair Conrad's neater answer to remove the slightly clumsy list processing from my previous version.

Dave Webb
A: 

Three versions in Smalltalk, from dumbest to correct.


In Smalltalk, = is the comparison operator:

isPalindrome: aString
    "Dumbest."
    ^ aString reverse = aString


The message #translateToLowercase returns the string as lowercase:

isPalindrome: aString
    "Case insensitive"
    |lowercase|
    lowercase := aString translateToLowercase.
    ^ lowercase reverse = lowercase


And in Smalltalk, strings are part of the Collection framework, you can use the message #select:thenCollect:, so here's the last version:

isPalindrome: aString
    "Case insensitive and keeping only alphabetic chars
    (blanks & punctuation insensitive)."
    |lowercaseLetters|
    lowercaseLetters := aString
        select: [:char | char isAlphabetic]
        thenCollect: [:char | char asLowercase]. 
    ^ lowercaseLetters reverse = lowercaseLetters
Sébastien RoccaSerra
+2  A: 

Another C++ one. Optimized for speed and size.

bool is_palindrome(const std::string& candidate) {
    for(std::string::const_iterator left = candidate.begin(), right = candidate.end(); left < --right ; ++left)
        if (*left != *right)
            return false;
    return true;
}

Leon Timmermans
A: 

In Ruby, converting to lowercase and stripping everything not alphabetic:

def isPalindrome( string )
    ( test = string.downcase.gsub( /[^a-z]/, '' ) ) == test.reverse
end

But that feels like cheating, right? No pointers or anything! So here's a C version too, but without the lowercase and character stripping goodness:

#include <stdio.h>
int isPalindrome( char * string )
{
    char * i = string;
    char * p = string;
    while ( *++i ); while ( i > p && *p++ == *--i );
    return i <= p && *i++ == *--p;
}
int main( int argc, char **argv )
{
    if ( argc != 2 )
    {
        fprintf( stderr, "Usage: %s <word>\n", argv[0] );
        return -1;
    }
    fprintf( stdout, "%s\n", isPalindrome( argv[1] ) ? "yes" : "no" );
    return 0;
}

Well, that was fun - do I get the job ;^)

MegaHAL
+7  A: 

I'm seeing a lot of incorrect answers here. Any correct solution needs to ignore whitespace and punctuation (and any non-alphabetic characters actually) and needs to be case insensitive.

A few good example test cases are:

"A man, a plan, a canal, Panama."

"A Toyota's a Toyota."

"A"

""

As well as some non-palindromes.

Example solution in C# (note: empty and null strings are considered palindromes in this design, if this is not desired it's easy to change):

public static bool IsPalindrome(string palindromeCandidate)
{
    if (string.IsNullOrEmpty(palindromeCandidate))
    {
        return true;
    }
    Regex nonAlphaChars = new Regex("[^a-z0-9]");
    string alphaOnlyCandidate = nonAlphaChars.Replace(palindromeCandidate.ToLower(), "");
    if (string.IsNullOrEmpty(alphaOnlyCandidate))
    {
        return true;
    }
    int leftIndex = 0;
    int rightIndex = alphaOnlyCandidate.Length - 1;
    while (rightIndex > leftIndex)
    {
        if (alphaOnlyCandidate[leftIndex] != alphaOnlyCandidate[rightIndex])
        {
            return false;
        }
        leftIndex++;
        rightIndex--;
    }
    return true;
}
Wedge
Shouldn't the regex be Regex nonAlphaChars = new Regex("[^a-zA-Z0-9]");So that we also take care of capitalized chars in the string
Learner
May be not..you have used ToLower....sorry I just missed it
Learner
You said: Any correct solution needs to ignore whitespace and punctuation (and any non-alphabetic characters actually) and needs to be case insensitive. What makes you think that this is true? Does anybody have a correct definition of a palindrome? Following the definition of the questionnee, I don't agree with you.
Fortega
+6  A: 

How about a (non-trivial) solution that itself is also a palindrome?

mweerden
+9  A: 

A more Ruby-style rewrite of Hal's Ruby version:

class String
  def palindrome?
    (test = gsub(/[^A-Za-z]/, '').downcase) == test.reverse
  end
end

Now you can call palindrome? on any string.

Brian Warshaw
+9  A: 

C in the house. (not sure if you didn't want a C example here)

bool IsPalindrome(char *s)
{
    int  i,d;
    int  length = strlen(s);
    char cf, cb;

    for(i=0, d=length-1 ; i < length && d >= 0 ; i++ , d--)
    {
     while(cf= toupper(s[i]), (cf < 'A' || cf >'Z') && i < length-1)i++;
     while(cb= toupper(s[d]), (cb < 'A' || cb >'Z') && d > 0       )d--;
     if(cf != cb && cf >= 'A' && cf <= 'Z' && cb >= 'A' && cb <='Z')
      return false;
    }
    return true;
}

That will return true for "racecar", "Racecar", "race car", "racecar ", and "RaCe cAr". It would be easy to modify to include symbols or spaces as well, but I figure it's more useful to only count letters(and ignore case). This works for all palindromes I've found in the answers here, and I've been unable to trick it into false negatives/positives.

Also, if you don't like bool in a "C" program, it could obviously return int, with return 1 and return 0 for true and false respectively.

Hostile
ofcourse, always loves the c solutions :)
Prakash
+1  A: 

Perl:

sub is_palindrome($)
{
  $s = lc(shift); # ignore case
  $s =~ s/\W+//g; # consider only letters, digits, and '_'
  $s eq reverse $s;
}

It ignores case and strips non-alphanumeric characters (it locale- and unicode- neutral).

Vertigo
+1  A: 

Using Java, using Apache Commons String Utils:

public boolean isPalindrome(String phrase) {
  phrase = phrase.toLowerCase().replaceAll("[^a-z]", "");
  return StringUtils.reverse(phrase).equals(phrase);
}
SCdF
A: 
Pedro
+1  A: 

I had to do this for a programming challenge, here's a snippet of my Haskell:

isPalindrome :: String -> Bool
isPalindrome n = (n == reverse n)
tj9991
+1  A: 

Python:

if s == s[::-1]: return True

Java:

if (s.Equals(s.Reverse())) { return true; }

PHP:

if (s == strrev(s)) return true;

Perl:

if (s == reverse(s)) { return true; }

Erlang:

string:equal(S, lists:reverse(S)).
Will Boyce
too bad i cant upvote you more than once ;)
Prakash
Hmm … what happens if this is `false`? No return value? Why the `if`s in the first place? Simply returning the expression works just as well.
Konrad Rudolph
Java Strings don't have a .Reverse() method (nor is .equals() capitalized).
Michael Myers
A: 

OCaml

let rec palindrome s =
  s = (tailrev s)

source

Prakash
A: 

I'm surprised there is no VB solutions yet :)

Prakash
+2  A: 

Lisp:

(defun palindrome(x) (string= x (reverse x)))
Alexander Stolz
A: 

boolean IsPalindrome(string s) { return s = s.Reverse(); }

LepardUK
+1  A: 

Perl:

sub is_palindrome {
    my $s = lc shift; # normalize case
    $s =~ s/\W//g;    # strip non-word characters
    return $s eq reverse $s;
}
Michael Carman
A: 

Damn. Didn't see someone already posted the trivial haskell-version :( Sorry.

+1  A: 

An obfuscated C version:

int IsPalindrome (char *s)
{
  char*a,*b,c=0;
  for(a=b=s;a<=b;c=(c?c==1?c=(*a&~32)-65>25u?*++a,1:2:c==2?(*--b&~32)-65<26u?3:2:c==3?(*b-65&~32)-(*a-65&~32)?*(b=s=0,a),4:*++a,1:0:*++b?0:1));
  return s!=0;
}

Skizz

Skizz
+2  A: 

Note that in the above C++ solutions, there was some problems.

One solution was inefficient because it passed an std::string by copy, and because it iterated over all the chars, instead of comparing only half the chars. Then, even when discovering the string was not a palindrome, it continued the loop, waiting its end before reporting "false".

The other was better, with a very small function, whose problem was that it was not able to test anything else than std::string. In C++, it is easy to extend an algorithm to a whole bunch of similar objects. By templating its std::string into "T", it would have worked on both std::string, std::wstring, std::vector and std::deque. But without major modification because of the use of the operator <, the std::list was out of its scope.

My own solutions try to show that a C++ solution won't stop at working on the exact current type, but will strive to work an anything that behaves the same way, no matter the type. For example, I could apply my palindrome tests on std::string, on vector of int or on list of "Anything" as long as Anything was comparable through its operator = (build in types, as well as classes).

Note that the template can even be extended with an optional type that can be used to compare the data. For example, if you want to compare in a case insensitive way, or even compare similar characters (like è, é, ë, ê and e).

Like king Leonidas would have said: "Templates ? This is C++ !!!"

So, in C++, there are at least 3 major ways to do it, each one leading to the other:

Solution A: In a c-like way

The problem is that until C++0X, we can't consider the std::string array of chars as contiguous, so we must "cheat" and retrieve the c_str() property. As we are using it in a read-only fashion, it should be ok...


bool isPalindromeA(const std::string & p_strText)
{
   if(p_strText.length() < 2) return true ;
   const char * pStart = p_strText.c_str() ;             
   const char * pEnd = pStart + p_strText.length() - 1 ; 

   for(; pStart < pEnd; ++pStart, --pEnd)
   {
      if(*pStart != *pEnd)
      {
         return false ;
      }
   }

   return true ;
}


Solution B: A more "C++" version

Now, we'll try to apply the same solution, but to any C++ container with random access to its items through operator []. For example, any std::basic_string, std::vector, std::deque, etc. Operator [] is constant access for those containers, so we won't lose undue speed.


template <typename T>
bool isPalindromeB(const T & p_aText)
{
   if(p_aText.empty()) return true ;
   typename T::size_type iStart = 0 ;
   typename T::size_type iEnd = p_aText.size() - 1 ;

   for(; iStart < iEnd; ++iStart, --iEnd)
   {
      if(p_aText[iStart] != p_aText[iEnd])
      {
         return false ;
      }
   }

   return true ;
}


Solution C: Template powah !

It will work with almost any unordered STL-like container with bidirectional iterators For example, any std::basic_string, std::vector, std::deque, std::list, etc. So, this function can be applied on all STL-like containers with the following conditions: 1 - T is a container with bidirectional iterator 2 - T's iterator points to a comparable type (through operator =)


template <typename T>
bool isPalindromeC(const T & p_aText)
{
   if(p_aText.empty()) return true ;
   typename T::const_iterator pStart = p_aText.begin() ;
   typename T::const_iterator pEnd = p_aText.end() ;
   --pEnd ;

   while(true)
   {
      if(*pStart != *pEnd)
      {
         return false ;
      }

      if((pStart == pEnd) || (++pStart == pEnd))
      {
         return true ;
      }

      --pEnd ;
   }
}


paercebal
Fancy. How big will the string have to be so that this method is faster than comparing with the reverse?
Svante
If you don't have the reverse, then you have to allocate and then create it by copying the data. I guess that comparing the reverse is always slower, but for curiosity's sake, I'm interested in any "comparing the reverse" implementation.
paercebal
None of these work because you don't ignore whitespace or punctuation.
John Dibling
@John Dibling: Even if I handled punctuation and whitespace, it wouldn't work in Unicode on Linux because of UTF-8. The aim of this code is show C++ code, not produce an industrial-strength function.
paercebal
A: 

c++:

bool is_palindrome(const string &s)
{
    return equal( s.begin(), s.begin()+s.length()/2, s.rbegin());
}
A: 

There isn't a single solution on here which takes into account that a palindrome can also be based on word units, not just character units.

Which means that none of the given solutions return true for palindromes like "Girl, bathing on Bikini, eyeing boy, sees boy eyeing bikini on bathing girl".

Here's a hacked together version in C#. I'm sure it doesn't need the regexes, but it does work just as well with the above bikini palindrome as it does with "A man, a plan, a canal-Panama!".

    static bool IsPalindrome(string text)
    {
        bool isPalindrome = IsCharacterPalindrome(text);
        if (!isPalindrome)
        {
            isPalindrome = IsPhrasePalindrome(text);
        }
        return isPalindrome;
    }

    static bool IsCharacterPalindrome(string text)
    {
        String clean = Regex.Replace(text.ToLower(), "[^A-z0-9]", String.Empty, RegexOptions.Compiled);
        bool isPalindrome = false;
        if (!String.IsNullOrEmpty(clean) && clean.Length > 1)
        {
            isPalindrome = true;
            for (int i = 0, count = clean.Length / 2 + 1; i < count; i++)
            {
                if (clean[i] != clean[clean.Length - 1 - i])
                {
                    isPalindrome = false; break;
                }
            }
        }
        return isPalindrome;
    }

    static bool IsPhrasePalindrome(string text)
    {
        bool isPalindrome = false;
        String clean = Regex.Replace(text.ToLower(), @"[^A-z0-9\s]", " ", RegexOptions.Compiled).Trim();
        String[] words = Regex.Split(clean, @"\s+");
        if (words.Length > 1)
        {
            isPalindrome = true;
            for (int i = 0, count = words.Length / 2 + 1; i < count; i++)
            {
                if (words[i] != words[words.Length - 1 - i])
                {
                    isPalindrome = false; break;
                }
            }
        }
        return isPalindrome;
    }
Shabbyrobe
A: 

I haven't seen any recursion yet, so here goes...

import re

r = re.compile("[^0-9a-zA-Z]")

def is_pal(s):

    def inner_pal(s):
        if len(s) == 0:
            return True
        elif s[0] == s[-1]:
            return inner_pal(s[1:-1])
        else:
            return False

    r = re.compile("[^0-9a-zA-Z]")
    return inner_pal(r.sub("", s).lower())
A: 

This is all good, but is there a way to do better algorithmically? I was once asked in a interview to recognize a palindrome in linear time and constant space.

I couldn't think of anything then and I still can't.

(If it helps, I asked the interviewer what the answer was. He said you can construct a pair of hash functions such that they hash a given string to the same value if and only if that string is a palindrome. I have no idea how you would actually make this pair of functions.)

+2  A: 

C++

std::string a = "god";
std::string b = "lol";

std::cout << (std::string(a.rbegin(), a.rend()) == a) << " " 
          << (std::string(b.rbegin(), b.rend()) == b);

Bash

function ispalin { [ "$( echo -n $1 | tac -rs . )" = "$1" ]; }
echo "$(ispalin god && echo yes || echo no), $(ispalin lol && echo yes || echo no)"

Gnu Awk

/* obvious solution */
function ispalin(cand, i) { 
    for(i=0; i<length(cand)/2; i++) 
        if(substr(cand, length(cand)-i, 1) != substr(cand, i+1, 1)) 
            return 0; 
    return 1; 
}

/* not so obvious solution. cough cough */
{ 
    orig = $0;
    while($0) { 
        stuff = stuff gensub(/^.*(.)$/, "\\1", 1); 
        $0 = gensub(/^(.*).$/, "\\1", 1); 
    }
    print (stuff == orig); 
}

Haskell

Some brain dead way doing it in Haskell

ispalin :: [Char] -> Bool
ispalin a = a == (let xi (y:my) = (xi my) ++ [y]; xi [] = [] in \x -> xi x) a

Plain English

"Just reverse the string and if it is the same as before, it's a palindrome"

Johannes Schaub - litb
A: 

The solutions which strip out any chars that don't fall between A-Z or a-z are very English centric. Letters with diacritics such as à or é would be stripped!

According to Wikipedia:

The treatment of diacritics varies. In languages such as Czech and Spanish, letters with diacritics or accents (except tildes) are not given a separate place in the alphabet, and thus preserve the palindrome whether or not the repeated letter has an ornamentation. However, in Swedish and other Nordic languages, A and A with a ring (å) are distinct letters and must be mirrored exactly to be considered a true palindrome.

So to cover many other languages it would be better to use collation to convert diacritical marks to their equivalent non diacritic or leave alone as appropriate and then strip whitespace and punctuation only before comparing.

reefnet_alex
A: 
set l = index of left most character in word
set r = index of right most character in word

loop while(l < r)
begin
  if letter at l does not equal letter at r
    word is not palindrome
  else
     increase l and decrease r
end
word is palindrome
Jason Lepack
A: 

Efficient C++ version:

template< typename Iterator >
bool is_palindrome( Iterator first, Iterator last, std::locale const& loc = std::locale("") )
{
    if ( first == last )
        return true;

    for( --last; first < last; ++first, --last )
    {
        while( ! std::isalnum( *first, loc ) && first < last )
            ++first;
        while( ! std::isalnum( *last, loc ) && first < last )
            --last;
        if ( std::tolower( *first, loc ) != std::tolower( *last, loc ) )
            return false;
    }
    return true;
}
Vadim Ferderer
A: 

Here are two more Perl versions, neither of which uses reverse. Both use the basic algorithm of comparing the first character of the string to the last, then discarding them and repeating the test, but they use different methods of getting at the individual characters (the first peels them off one at a time with a regex, the second splits the string into an array of characters).

#!/usr/bin/perl

my @strings = ("A man, a plan, a canal, Panama.", "A Toyota's a Toyota.", 
               "A", "", "As well as some non-palindromes.");

for my $string (@strings) {
  print is_palindrome($string)  ? "'$string' is a palindrome (1)\n"
                                : "'$string' is not a palindrome (1)\n";
  print is_palindrome2($string) ? "'$string' is a palindrome (2)\n"
                                : "'$string' is not a palindrome (2)\n";
} 

sub is_palindrome {
  my $str = lc shift;
  $str =~ tr/a-z//cd;

  while ($str =~ s/^(.)(.*)(.)$/\2/) {
    return unless $1 eq $3;
  }

  return 1;
} 

sub is_palindrome2 {
  my $str = lc shift;
  $str =~ tr/a-z//cd;
  my @chars = split '', $str;

  while (@chars && shift @chars eq pop @chars) {};

  return scalar @chars <= 1;
}
Dave Sherohman
A: 

Easy mode in C#, only using Base Class Libraries

Edit: just saw someone did Array.Reverse also

public bool IsPalindrome(string s)
            {
                if (String.IsNullOrEmpty(s))
                {
                    return false;
                }

                else
                {
                    char[] t = s.ToCharArray();
                    Array.Reverse(t);
                    string u = new string(t);
                    if (s.ToLower() == u.ToLower())
                    {
                        return true;
                    }
                }

                return false;
            }
RandomNoob
A: 

Here's another for C# that I used when doing a sample server control. It can be found in the book ASP.NET 3.5 Step by Step (MS Press). It's two methods, one to strip non-alphanumerics, and another to check for a palindrome.

protected string StripNonAlphanumerics(string str)
{
    string strStripped = (String)str.Clone();
    if (str != null)
    {
        char[] rgc = strStripped.ToCharArray();
        int i = 0;
        foreach (char c in rgc)
        {
            if (char.IsLetterOrDigit(c))
            {
                i++;
            }
            else
            {
                strStripped = strStripped.Remove(i, 1);
            }
        }
    }
    return strStripped;
}
protected bool CheckForPalindrome()
{
    if (this.Text != null)
    {
        String strControlText = this.Text;
        String strTextToUpper = null;
        strTextToUpper = Text.ToUpper();
        strControlText =
                    this.StripNonAlphanumerics(strTextToUpper);
        char[] rgcReverse = strControlText.ToCharArray();
        Array.Reverse(rgcReverse);
        String strReverse = new string(rgcReverse);
        if (strControlText == strReverse)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    else
    {
        return false;
    }
}
BBetances
A: 

Const-correct C/C++ pointer solution. Minimal operations in loop.

int IsPalindrome (const char *str)
{
    const unsigned len = strlen(str);
    const char *end = &str[len-1];
    while (str < end)
        if (*str++ != *end--)
            return 0;
    return 1;
}
hughdbrown
+1  A: 

A simple Java solution:

public boolean isPalindrome(String testString) {
    StringBuffer sb = new StringBuffer(testString);
    String reverseString = sb.reverse().toString();

    if(testString.equalsIgnoreCase(reverseString)) {
        return true;
    else {
        return false;
    }
}
Ascalonian
A: 

How come no one has posted a recursive solution yet? hmmm ....

armahg
+1  A: 

My 2c. Avoids overhead of full string reversal everytime, taking advantage of shortcircuiting to return as soon as the nature of the string is determined. Yes, you should condition your string first, but IMO that's the job of another function.

In C#

    /// <summary>
    /// Tests if a string is a palindrome
    /// </summary>
    public static bool IsPalindrome(this String str)
    {
        if (str.Length == 0) return false;
        int index = 0;
        while (index < str.Length / 2)
            if (str[index] != str[str.Length - ++index]) return false;

        return true;
    }
patjbs
+1  A: 

Ruby:

class String
    def is_palindrome?
        letters_only = gsub(/\W/,'').downcase
        letters_only == letters_only.reverse
    end
end

puts 'abc'.is_palindrome? # => false
puts 'aba'.is_palindrome? # => true
puts "Madam, I'm Adam.".is_palindrome? # => true
Matchu
A: 

Scala

def pal(s:String) = Symbol(s) equals Symbol(s.reverse)
Alexander Stolz
+1  A: 

Prolog

palindrome(B, R) :-
palindrome(B, R, []).

palindrome([], R, R).
palindrome([X|B], [X|R], T) :-
palindrome(B, R, [X|T]).
AlejandroR
shouldn't it be with only one argument? something like:palindrome(L) :- palindrome(L, []).palindrome(L, L).palindrome([_, L], L).palindrome([X|R], L) :- palindrome(R, [X|L]).
Chris
A: 
    public bool IsPalindrome(string s)
    {
        string formattedString = s.Replace(" ", string.Empty).ToLower();
        for (int i = 0; i < formattedString.Length / 2; i++)
        {
            if (formattedString[i] != formattedString[formattedString.Length - 1 - i])
                return false;
        }
        return true;
    }

This method will work for sting like "Was it a rat I saw". But I feel we need to eliminate special character through Regex.

Pritam Karmakar
A: 

C# Version:

Assumes MyString to be a char[], Method return after verification of the string, it ignores space and <,>, but this can be extended to ignore more, probably impleemnt a regex match of ignore list.

public bool IsPalindrome()
            if (MyString.Length == 0)
                return false;

            int len = MyString.Length - 1;

            int first = 0;
            int second = 0;

            for (int i = 0, j = len; i <= len / 2; i++, j--)
            {
                while (i<j && MyString[i] == ' ' || MyString[i] == ',')
                    i++;

                while(j>i && MyString[j] == ' ' || MyString[j] == ',')
                    j--;

                if ((i == len / 2) && (i == j))
                    return true;

                first = MyString[i] >= 97 && MyString[i] <= 122 ? MyString[i] - 32 : MyString[i];
                second = MyString[j] >= 97 && MyString[j] <= 122 ? MyString[j] - 32 : MyString[j];

                if (first != second)
                    return false;
            }

            return true;
  }

Quick test cases

negative 1. ABCDA 2. AB CBAG 3. A#$BDA 4. NULL/EMPTY

positive 1. ABCBA 2. A, man a plan a canal,,Panama 3. ABC BA 4. M 5. ACCB

let me know any thoghts/errors.