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

--  Fun With Palindromes Query 1.01
--  This is the brute-force method of character removal.
--  Use this method only if you have a limited number of distinct,
--  known characters to remove
 
DECLARE
    @Phrase                 VARCHAR(50),
    @Phrase_LettersOnly     VARCHAR(50);
 
SET @Phrase = 'A man, a plan, a canal, Panama!';
 
SET @Phrase_LettersOnly = REPLACE(REPLACE(REPLACE(@Phrase, ' ', ''), ',', ''), '!', '');
 
PRINT @Phrase_LettersOnly;

 

 

 

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:

--  Fun With Palindromes Query 1.02
--  Using a tally table to separate out the characters in the string
--  and keeping only those that fall in the desired ASCII range.

USE Admin;
GO

DECLARE
    @Phrase                 VARCHAR(50),
    @Phrase_LettersOnly     VARCHAR(50);

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


SELECT
    SUBSTRING(@Phrase, Tl.SequenceNumber, 1)
FROM
    dbo.Tally Tl
WHERE
    Tl.SequenceNumber <= LEN(@Phrase)
    AND
    (ASCII(SUBSTRING(@Phrase, Tl.SequenceNumber, 1)) BETWEEN 65 AND 90
        OR
        ASCII(SUBSTRING(@Phrase, Tl.SequenceNumber, 1)) BETWEEN 97 AND 122)
ORDER BY
    Tl.SequenceNumber;

 

 

 

 

 

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:

--  Fun With Palindromes Query 1.03
--  Using ROW_NUMBER() against the sys.objects DMO.

SELECT
    SequenceNumber = ROW_NUMBER() OVER (ORDER BY name)
FROM
    sys.objects;

 

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

--  Fun With Palindromes Query 1.04
--  Using ROW_NUMBER() against the sys.objects in a CTE instead
--  of a physical tally table.

DECLARE
    @Phrase                 VARCHAR(50),
    @Phrase_LettersOnly     VARCHAR(50);

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


WITH Tally AS
(
    SELECT
        SequenceNumber = ROW_NUMBER() OVER (ORDER BY name)
    FROM
        sys.objects
)
SELECT
    SUBSTRING(@Phrase, Tl.SequenceNumber, 1)
FROM
    Tally Tl
WHERE
    Tl.SequenceNumber <= LEN(@Phrase)
    AND
    (ASCII(SUBSTRING(@Phrase, Tl.SequenceNumber, 1)) BETWEEN 65 AND 90
        OR
        ASCII(SUBSTRING(@Phrase, Tl.SequenceNumber, 1)) BETWEEN 97 AND 122)
ORDER BY
    Tl.SequenceNumber;

 

 

 

 

 

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:

--  Fun With Palindromes Query 1.05
--  Using CONCAT() to put the letters-only string back together.

USE Admin;
GO

DECLARE
    @Phrase                 VARCHAR(50),
    @Phrase_LettersOnly     VARCHAR(50);

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


SELECT
    @Phrase_LettersOnly = CONCAT(@Phrase_LettersOnly, SUBSTRING(@Phrase, Tl.SequenceNumber, 1))
FROM
    dbo.Tally Tl
WHERE
    Tl.SequenceNumber <= LEN(@Phrase)
    AND
    (ASCII(SUBSTRING(@Phrase, Tl.SequenceNumber, 1)) BETWEEN 65 AND 90
        OR
        ASCII(SUBSTRING(@Phrase, Tl.SequenceNumber, 1)) BETWEEN 97 AND 122)
ORDER BY
    Tl.SequenceNumber;


PRINT @Phrase_LettersOnly;

 

 

 

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:

--  Fun With Palindromes Query 1.06
--  Using STUFF() and FOR XML PATH to put the letters-only string
--  back together.

USE Admin;
GO

DECLARE
    @Phrase                 VARCHAR(50),
    @Phrase_LettersOnly     VARCHAR(50);

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


SELECT
	@Phrase_LettersOnly = STUFF((
                                SELECT
                                    SUBSTRING(@Phrase, Tl.SequenceNumber, 1)
                                FROM
                                    dbo.Tally Tl
                                WHERE
                                    Tl.SequenceNumber <= LEN(@Phrase)
                                    AND
                                    (ASCII(SUBSTRING(@Phrase, Tl.SequenceNumber, 1)) BETWEEN 65 AND 90
                                        OR
                                        ASCII(SUBSTRING(@Phrase, Tl.SequenceNumber, 1)) BETWEEN 97 AND 122)
                                ORDER BY
                                    Tl.SequenceNumber
                                FOR XML PATH('')), 1, 0, '');


PRINT @Phrase_LettersOnly;

 

 

 

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:

--  Fun With Palindromes Query 1.07
--  Using STRING_AGG() to put the letters-only string back together.

USE Admin;
GO

DECLARE
    @Phrase                 VARCHAR(50),
    @Phrase_LettersOnly     VARCHAR(50);

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


SELECT
    @Phrase_LettersOnly = STRING_AGG(SUBSTRING(@Phrase, Tl.SequenceNumber, 1), '') WITHIN GROUP (ORDER BY Tl.SequenceNumber)
FROM
    dbo.Tally Tl
WHERE
    Tl.SequenceNumber <= LEN(@Phrase)
    AND
    (ASCII(SUBSTRING(@Phrase, Tl.SequenceNumber, 1)) BETWEEN 65 AND 90
        OR
        ASCII(SUBSTRING(@Phrase, Tl.SequenceNumber, 1)) BETWEEN 97 AND 122);


PRINT @Phrase_LettersOnly;

 

 

 

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!