57

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.

6
  • 20
    A man, a plan, a canal, Panama
    – Jonathan
    Sep 9, 2008 at 14:26
  • 22
    Go hang a salami. I'm a lasagna hog.
    – xanadont
    Sep 9, 2008 at 14:44
  • 4
    Do you care about punctuation? Case? What about locale-sensitive case folding?
    – erickson
    Sep 9, 2008 at 15:19
  • well, i didnt think of punctuation issues which could be ignored!
    – prakash
    Sep 11, 2008 at 14:43
  • 3
    I'm disappointed that, as far as I can tell, no one implemented it with a stack. Sep 7, 2011 at 3:54

69 Answers 69

1

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

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

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)).
3
  • Hmm … what happens if this is false? No return value? Why the ifs in the first place? Simply returning the expression works just as well. Sep 12, 2008 at 16:03
  • 1
    Java Strings don't have a .Reverse() method (nor is .equals() capitalized).
    – Michael Myers
    Dec 16, 2008 at 15:03
  • None of this does't works, there's not a single validation... try this: "A Santa at NASA"
    – Azteca
    Sep 25, 2015 at 2:48
1

Perl:

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

c++:

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

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).

1

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

Prolog

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

palindrome([], R, R).
palindrome([X|B], [X|R], T) :-
palindrome(B, R, [X|T]).
3
  • 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]).
    – Kru
    May 23, 2010 at 15:32
  • @Kru how does it handle palindromes like "121"?
    – Ram
    Nov 18, 2011 at 11:25
  • typing mistake... replace palindrome([_,L],L). by palindrome([_|L],L). So, palindrome("121", []) -> palindrome("21", "1") = palindrome([2|"1"], "1") which matches the corrected fact.
    – Kru
    Nov 18, 2011 at 16:17
1

Erlang is awesome

palindrome(L) -> palindrome(L,[]).

palindrome([],_) -> false;
palindrome([_|[]],[]) -> true;
palindrome([_|L],L) -> true;
palindrome(L,L) -> true;
palindrome([H|T], Acc) -> palindrome(T, [H|Acc]).
1

No solution using JavaScript yet?

function palindrome(s) {
  var l = 0, r = s.length - 1;
  while (l < r) if (s.charAt(left++) !== s.charAt(r--)) return false;
  return true
}
1
  • Most Javascript examples use s === s.split('').reverse().join('') ... kudos for efficiency :) Nov 24, 2013 at 7:39
1

Simple JavaScript solution. Run code snippet for demo.

function checkPalindrome(line){
      reverse_line=line.split("").reverse().join("");
      return line==reverse_line;
  }
alert("checkPalindrome(radar): "+checkPalindrome("radar"));

0

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;
}
1
  • The only difference is that my code treats empty string as a palindrome. That is by design.
    – gabr
    Sep 9, 2008 at 14:52
0

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;
}
1
  • 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
    Sep 10, 2008 at 0:33
0

If we're looking for numbers and simple words, many correct answers have been given.

However, if we're looking for what we generally see as palindromes in written language (e.g., "A dog, a panic, in a pagoda!"), the correct answer would be to iterate starting from both ends of the sentence, skipping non-alphanumeric characters individually, and returning false if any mismatches are found.

i = 0; j = length-1;

while( true ) {
  while( i < j && !is_alphanumeric( str[i] ) ) i++;
  while( i < j && !is_alphanumeric( str[j] ) ) j--;

  if( i >= j ) return true;

  if( tolower(string[i]) != tolower(string[j]) ) return false;
  i++; j--;
}

Of course, stripping out non-valid characters, reversing the resulting string and comparing it to the original one also works. It comes down to what type of language you're working on.

0

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

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.)

0

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.

0
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
0

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

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

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

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

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

Scala

def pal(s:String) = Symbol(s) equals Symbol(s.reverse)
0
    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.

0

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.

1
  • You say "ACCB" (number 5) comes back positive... is that correct? Nov 24, 2013 at 7:41
0
public static boolean isPalindrome( String str ) {
    int count = str.length() ;
    int i, j = count - 1 ;
    for ( i = 0 ; i < count ; i++ ) {
        if ( str.charAt(i) != str.charAt(j) ) return false ;
        if ( i == j ) return true ;
        j-- ;
    }
    return true ;
}
0
boolean IsPalindrome(string s) {
return s = s.Reverse();
}
0

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())
0

If you can use Java APIs and additional storage:

public static final boolean isPalindromeWithAdditionalStorage(String string) {
    String reversed = new StringBuilder(string).reverse().toString();
    return string.equals(reversed);
}

In can need an in-place method for Java:

public static final boolean isPalindromeInPlace(String string) {
    char[] array = string.toCharArray();
    int length = array.length-1;
    int half = Math.round(array.length/2);
    char a,b;
    for (int i=length; i>=half; i--) {
        a = array[length-i];
        b = array[i];
        if (a != b) return false;
    }
    return true;
}
0

Regular Approach:

flag = True // Assume palindrome is true
for i from 0 to n/2 
 { compare element[i] and element[n-i-1] // 0 to n-1
   if not equal set flag = False
   break }
return flag

There is a better machine optimized method which uses XORs but has the same complexity

XOR approach:

n = length of string
mid_element = element[n/2 +1]
for i from 0 to n
{ t_xor = element[i] xor element[i+1] }
if n is odd compare mid_element and t_xor
else check t_xor is zero

Not the answer you're looking for? Browse other questions tagged or ask your own question.