Fun With Palindromes – Part 1

I was thinking about algorithms yesterday afternoon – yes, I am a strange one – and one thought led to another and soon I found myself contemplating palindromes – words or phrases that read the same forwards and backwards, such as “racecar” or Napoleon’s famous – albeit apochryphal – “Able was I ere I saw Elba!”  Specifically, I was wondering what would be the most efficient way to test a string’s palindromicity using T-SQL.

Immediately I realized that this algorithm will need to accomplish two different things.  I first need to remove all non-alphabetic characters from the string I am testing, because while “able was I ere I saw Elba” is palindromic even leaving the spaces intact, this will not work for other well-known palindromes such as “A man, a plan, a canal, Panama!”  Then the second task is to check that the remaining string is the same front-to-back as it is back-to-front.

With the help of Elder’s Dead Roots Stirring album I set out to find the most efficient T-SQL code to accomplish this task.  My plan was to avoid resorting to Google for the answer, but perhaps in a future post I will go back and compare my solution to the best one I can find online.  For this first post in the series I will tackle only the first task of removing the non-alphabetic characters from the string.

I’ll readily admit to not being well versed in the use of regular expressions, so in order to meet my Google-free objective I’ll have to find another solution for now.  Let’s start by seeing what we can do with the famed “A man, a plan, a canal, Panama!”  Because I know exactly which characters are in this string, I can use the brute-force method of nested REPLACE() functions to parse them out – see line 11 below.  (You may want to use the Toggle Line Wrap or Open Code In New Window options to see it better.)

 

 

 

Of course I may not always have the luxury of knowing the contents of the string beforehand.  I do know that the characters I want to keep will fall within the range of A-Z (ASCII values 65-90) or a-z (ASCII values 97-122).  My plan is to step through the string one character at a time, but instead of using a WHILE loop, I’ll instead use the tally table (a table of sequential numbers) in my Admin database like so:

 

 

 

 

 

If for some reason you don’t have or are not able to add a tally table to your system, you can use the ROW_NUMBER() function against the sys.objects DMO instead:

 

You can put this code into a common table expression and combine it with the second query:

 

 

 

 

 

Of course, separate rows for each character don’t help us very much.  Let’s use the CONCAT() function to put them back into a single string:

 

 

 

This method works great to parse a single string, but I will have a whole table of potential palindromes to parse.  Historically, I would usually use the STUFF() function with FOR XML PATH to reassemble the strings like this:

 

 

 

I’ve always found using this method to be a bit non-intuitive and fiddly.  Thankfully SQL Server 2017 has added a new function called STRING_AGG() that we can use instead:

 

 

 

Wow, that’s a lot of queries, so I’ll bring part one of this series to a close.  I look forward to seeing some other solutions in the comments below.  In part two, we’ll compare the performance of these methods across both a single string, and a whole table of them!

 

4 Replies to “Fun With Palindromes – Part 1”

  1. –Quick and dirty (I use SQL 2014)
    –You can tell i am an old VB developer!
    DECLARE @Phrase VARCHAR(50),
    @Phrase_Temp VARCHAR(50),
    @Phrase_LettersOnly VARCHAR(50) = ”,
    @Initcnt INT,
    @cnt INT = 0;

    SET @Phrase = ‘A man, a plan, a canal, Panama!’;

    — remove any spaces and convert ALL to uppercase
    SET @Phrase_Temp = REPLACE(UPPER(@Phrase), ‘ ‘, ”);
    SET @Initcnt = LEN(@Phrase_Temp);

    — strip out any NON Letters
    WHILE @cnt < @Initcnt
    BEGIN
    SET @cnt = @cnt + 1;
    IF ASCII(SUBSTRING(@Phrase_Temp, @cnt, 1)) BETWEEN 65 AND 90 OR ASCII(SUBSTRING(@Phrase_Temp, @cnt, 1)) BETWEEN 48 AND 57
    BEGIN
    SET @Phrase_LettersOnly =
    @Phrase_LettersOnly + SUBSTRING(@Phrase_Temp, @cnt, 1);
    END;
    END;
    IF REVERSE(@Phrase_LettersOnly) = @Phrase_LettersOnly
    PRINT 'This is a pallandrome';
    ELSE PRINT 'This is NOT a pallandrome';

Leave a Reply

Your email address will not be published. Required fields are marked *