How to check that a string is a palindrome using regular expressions?

The answer to this question is that "it is impossible". More specifically, the interviewer is wondering if you paid attention in your computational theory class.

In your computational theory class you learned about finite state machines. A finite state machine is composed of nodes and edges. Each edge is annotated with a letter from a finite alphabet. One or more nodes are special "accepting" nodes and one node is the "start" node. As each letter is read from a given word we traverse the given edge in the machine. If we end up in an accepting state then we say that the machine "accepts" that word.

A regular expression can always be translated into an equivalent finite state machine. That is, one that accepts and rejects the same words as the regular expression (in the real world, some regexp languages allow for arbitrary functions, these don't count).

It is impossible to build a finite state machine that accepts all palindromes. The proof relies on the facts that we can easily build a string that requires an arbitrarily large number of nodes, namely the string

a^x b a^x (eg., aba, aabaa, aaabaaa, aaaabaaaa, ....)

where a^x is a repeated x times. This requires at least x nodes because, after seeing the 'b' we have to count back x times to make sure it is a palindrome.

Finally, getting back to the original question, you could tell the interviewer that you can write a regular expression that accepts all palindromes that are smaller than some finite fixed length. If there is ever a real-world application that requires identifying palindromes then it will almost certainly not include arbitrarily long ones, thus this answer would show that you can differentiate theoretical impossibilities from real-world applications. Still, the actual regexp would be quite long, much longer than equivalent 4-line program (easy exercise for the reader: write a program that identifies palindromes).

While the PCRE engine does support recursive regular expressions (see the answer by Peter Krauss), you cannot use a regex on the ICU engine (as used, for example, by Apple) to achieve this without extra code. You'll need to do something like this:

This detects any palindrome, but does require a loop (which will be required because regular expressions can't count).

$a = "teststring";
while(length $a > 1)
{
   $a =~ /(.)(.*)(.)/;
   die "Not a palindrome: $a" unless $1 eq $3;
   $a = $2;
}
print "Palindrome";

It's not possible. Palindromes aren't defined by a regular language. (See, I DID learn something in computational theory)

With Perl regex:

/^((.)(?1)\2|.?)$/

Though, as many have pointed out, this can't be considered a regular expression if you want to be strict. Regular expressions does not support recursion.

Here's one to detect 4-letter palindromes (e.g.: deed), for any type of character:

\(.\)\(.\)\2\1

Here's one to detect 5-letter palindromes (e.g.: radar), checking for letters only:

\([a-z]\)\([a-z]\)[a-z]\2\1

So it seems we need a different regex for each possible word length. This post on a Python mailing list includes some details as to why (Finite State Automata and pumping lemma).

Depending on how confident you are, I'd give this answer:

I wouldn't do it with a regular expression. It's not an appropriate use of regular expressions.

Recursive Regular Expressions can do it!

So simple and self-evident algorithm to detect a string that contains a palindrome:

   (\w)(?:(?R)|\w?)\1

At rexegg.com/regex-recursion the tutorial explains how it works.

It works fine with any language, here an example adapted from the same source (link) as proof-of-concept, using PHP:

$subjects=['dont','o','oo','kook','book','paper','kayak','okonoko','aaaaa','bbbb'];
$pattern='/(\w)(?:(?R)|\w?)\1/';
foreach ($subjects as $sub) {
  echo $sub." ".str_repeat('-',15-strlen($sub))."-> ";
  if (preg_match($pattern,$sub,$m)) 
      echo $m[0].(($m[0]==$sub)? "! a palindrome!\n": "\n");
  else 
      echo "sorry, no match\n";
}

outputs

dont ------------> sorry, no match
o ---------------> sorry, no match
oo --------------> oo! a palindrome!
kook ------------> kook! a palindrome!
book ------------> oo
paper -----------> pap
kayak -----------> kayak! a palindrome!
okonoko ---------> okonoko! a palindrome!
aaaaa -----------> aaaaa! a palindrome!
bbbb ------------> bbb

Comparing

The regular expression ^((\w)(?:(?1)|\w?)\2)$ do the same job, but as yes/not instead "contains".
PS: it is using a definition where "o" is not a palimbrome, "able-elba" hyphened format is not a palindrome, but "ableelba" is. Naming it definition1.
When "o" and "able-elba" are palindrones, naming definition2.

Comparing with another "palindrome regexes",

• ^((.)(?:(?1)|.?)\2)$ the base-regex above without \w restriction, accepting "able-elba".

• ^((.)(?1)?\2|.)$ (@LilDevil) Use definition2 (accepts "o" and "able-elba" so differing also in the recognition of "aaaaa" and "bbbb" strings).

• ^((.)(?1)\2|.?)$ (@Markus) not detected "kook" neither "bbbb"

• ^((.)(?1)*\2|.?)$ (@Csaba) Use definition2.

NOTE: to compare you can add more words at $subjects and a line for each compared regex,

  if (preg_match('/^((.)(?:(?1)|.?)\2)$/',$sub)) echo " ...reg_base($sub)!\n";
  if (preg_match('/^((.)(?1)?\2|.)$/',$sub)) echo " ...reg2($sub)!\n";
  if (preg_match('/^((.)(?1)\2|.?)$/',$sub)) echo " ...reg3($sub)!\n";
  if (preg_match('/^((.)(?1)*\2|.?)$/',$sub)) echo " ...reg4($sub)!\n";

It's actually easier to do it with string manipulation rather than regular expressions:

bool isPalindrome(String s1)

{

    String s2 = s1.reverse;

    return s2 == s1;
}

I realize this doesn't really answer the interview question, but you could use it to show how you know a better way of doing a task, and you aren't the typical "person with a hammer, who sees every problem as a nail."

Regarding the PCRE expression (from MizardX):

/^((.)(?1)\2|.?)$/

Have you tested it? On my PHP 5.3 under Win XP Pro it fails on: aaaba Actually, I modified the expression expression slightly, to read:

/^((.)(?1)*\2|.?)$/

I think what is happening is that while the outer pair of characters are anchored, the remaining inner ones are not. This is not quite the whole answer because while it incorrectly passes on "aaaba" and "aabaacaa", it does fail correctly on "aabaaca".

I wonder whether there a fixup for this, and also, Does the Perl example (by JF Sebastian / Zsolt) pass my tests correctly?

Csaba Gabor from Vienna

In Perl (see also Zsolt Botykai's answer):

$re = qr/
  .                 # single letter is a palindrome
  |
  (.)               # first letter
  (??{ $re })??     # apply recursivly (not interpolated yet)
  \1                # last letter
/x;

while(<>) {
    chomp;
    say if /^$re$/; # print palindromes
}

As pointed out by ZCHudson, determine if something is a palindrome cannot be done with an usual regexp, as the set of palindrome is not a regular language.

I totally disagree with Airsource Ltd when he says that "it's not possibles" is not the kind of answer the interviewer is looking for. During my interview, I come to this kind of question when I face a good candidate, to check if he can find the right argument when we proposed to him to do something wrong. I do not want to hire someone who will try to do something the wrong way if he knows better one.

something you can do with perl: http://www.perlmonks.org/?node_id=577368

I would explain to the interviewer that the language consisting of palindromes is not a regular language but instead context-free.

The regular expression that would match all palindromes would be infinite. Instead I would suggest he restrict himself to either a maximum size of palindromes to accept; or if all palindromes are needed use at minimum some type of NDPA, or just use the simple string reversal/equals technique.

I don't have the rep to comment inline yet, but the regex provided by MizardX, and modified by Csaba, can be modified further to make it work in PCRE. The only failure I have found is the single-char string, but I can test for that separately.

/^((.)(?1)?\2|.)$/

If you can make it fail on any other strings, please comment.

This regex will detect palindromes up to 22 characters ignoring spaces, tabs, commas, and quotes.

\b(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*(?:(\w)[ \t,'"]*\11?[ \t,'"]*\10|\10?)[ \t,'"]*\9|\9?)[ \t,'"]*\8|\8?)[ \t,'"]*\7|\7?)[ \t,'"]*\6|\6?)[ \t,'"]*\5|\5?)[ \t,'"]*\4|\4?)[ \t,'"]*\3|\3?)[ \t,'"]*\2|\2?))?[ \t,'"]*\1\b

Play with it here: https://regexr.com/4tmui

I wrote an explanation of how I got that here: https://medium.com/analytics-vidhya/coding-the-impossible-palindrome-detector-with-a-regular-expressions-cd76bc23b89b

In JavaScript it is done by typing

          function palindrome(str) {
  var symbol = /\W|_/g;
  str = str.replace(symbol, "").toLowerCase();
  var palindrome = str.split("").reverse("").join("");
  return (str === palindrome);
}