Can Regular Expressions Determine Palindromes?

Help & Support
1

Recently, I came across a question in a book that piqued my interest: Is it possible to use regular expressions to determine whether a string is a palindrome? For those who may not be familiar, a palindrome is a string that reads the same forwards and backwards, with the possibility of having a single unique character in the middle.

def palindrome?(str : String) : Bool
  str == str.reverse
end

The book I was reading engaged in a discussion on this topic and concluded that palindromes do not conform to the grammar of regular expressions , and therefore, it is not possible to construct a regular expression that can determine whether a string is a palindrome. The reasoning provided was based on the fact that regular expressions are not capable of handling the nested or recursive nature required to compare characters equidistant from the center of the string. It further explains that the most efficient method to determine whether a string is a palindrome is to scan the string from both ends towards the center , comparing corresponding characters. Here is the implementation in Crystal:

def palindrome?(str : String) : Bool
  left = 0
  right = str.size - 1

  while left < right
    return false if str[left] != str[right]
    left &+= 1
    right &-= 1
  end

  true
end

However, after several attempts and some experimentation, I believe I have come up with a regular expression pattern that seems to work for determining palindromes. Here is the pattern I have devised:

palindrome1 = "ć—Ą6 6yyyy6 6ć—Ą"
pattern = /^(.?|(.)(?1)\2)$/
pattern.matches? palindrome1
2

Most “regular expression” libraries, especially ones with backreferences, are more expressive than regular expressions in the formal sense (only *, |, and ()).

1 Like
3

Crystal uses PCRE2, which supports recursive patterns.

https://www.pcre.org/current/doc/html/pcre2pattern.html#recursion

There are many examples if you search the internet for “pcre palindrome”

1 Like
4

Ruby support.

 ╰──➤ $ pry
[1] pry(main)> "abba".match? /(.)(.)\k<-1>\k<-2>/
=> true

Crystal use PCRE2, it probably not as powerful as regular expressions in Ruby.

1 Like
5

In my opinion this would be a subset of what is generally considered a palindrome. For example, “taco cat” is considered a palindrome, but the regex or str == str.reverse would fail because of the space. You would have to remove spaces first, or specify that it only detects single words, not sentences.