Test if a string is a palindrome using T-SQL

Question

I am a beginner in T-SQL. I want to decide whether an input string is a palindrome, with output = 0 if it is not and output = 1 if it is. I am still figuring out the syntax. I am not even getting an error message. I am looking for different solutions and some feedback, to gain a better understanding and knowledge of how T-SQL works, to become better at it --I am still a student.

The key idea, as I see it, is to compare the left- and right- most characters to each other, to check for equality, then go on to compare the second character from the left with the 2nd-from last one, etc. We do a loop: If the characters are equal to each other, we continue. If we reached the end, we output 1, if not, we output 0.

Would you please critique:

CREATE function Palindrome(
    @String  Char
    , @StringLength  Int
    , @n Int
    , @Palindrome BIN
    , @StringLeftLength  Int
)
RETURNS Binary
AS
BEGIN
SET @ n=1
SET @StringLength= Len(String)

  WHILE @StringLength - @n >1

  IF
  Left(String,@n)=Right(String, @StringLength)

 SET @n =n+1
 SET @StringLength =StringLength -1

 RETURN @Binary =1

 ELSE RETURN @Palindrome =0

END

I think I am on the right track, but I am still a long way off. Any ideas?

Answer 1

Since there are a fair number of solutions I'm going to go with the "critique" part of your question. A couple of notes: I've fixed some typos and noted where I did. If I'm wrong about them being a typo mention it in the comments and I'll explain what's going on. I'm going to point out several things that you may already know, so please don't take offense if I did. Some comments may seem picky but I don't know where you are in your journey so have to assume you are just starting out.

CREATE function Palindrome (
    @String  Char
    , @StringLength  Int
    , @n Int
    , @Palindrome BIN
    , @StringLeftLength  Int

ALWAYS include the length with a char or varchar definition. Aaron Bertrand talks about it in depth here. He is talking about varchar but the same goes for char. I'd use a varchar(255) for this if you only want relatively short strings or maybe a varchar(8000) for larger ones or even varchar(max). Varchar is for variable length strings char is only for fixed ones. Since you aren't sure of the length of string being passed in use varchar. Also it's binary not bin.

Next you don't need to put all of those variables as parameters. Declare them within your code. Only put something in the parameter list if you plan on passing it in or out. (You'll see how this looks at the end.) Also you have @StringLeftLength but never use it. So I'm not going to declare it.

The next thing I'm going to do is re-format a bit to make a few things obvious.

BEGIN
    SET @n=1
    SET @StringLength = Len(@String) -- Missed an @

    WHILE @StringLength - @n >1 
        IF Left(@String,@n)=Right(@String, @StringLength) -- More missing @s
            SET @n = @n + 1 -- Another missing @

    SET @StringLength = @StringLength - 1  -- Watch those @s :)

    RETURN @Palindrome = 1 -- Assuming another typo here 

    ELSE 
        RETURN @Palindrome =0

END

If you look at the way I did the indenting you'll notice that I have this:

    WHILE @StringLength - @n >1 
        IF Left(@String,@n)=Right(@String, @StringLength)
            SET @n = @n + 1

That's because commands like WHILE and IF only affect the first line of code after them. You have to use a BEGIN .. END block if you want multiple commands. So fixing that we get:

    WHILE @StringLength - @n > 1 
        IF Left(@String,@n)=Right(@String, @StringLength)
            BEGIN 
                SET @n = @n + 1
                SET @StringLength = @StringLength - 1
                RETURN @Palindrome = 1 
            END
        ELSE 
            RETURN @Palindrome = 0

You'll notice that I only added a BEGIN .. END block in the IF. That's because even though the IF statement is multiple lines long (and even contains multiple commands) it is still a single statement (covering everything performed in the IF and the ELSE portions of the statement).

Next you'll get an error after both of your RETURNs. You can return a variable OR a literal. You can't set the variable and return it at the same time.

                SET @Palindrome = 1 
            END
        ELSE 
            SET @Palindrome = 0

    RETURN @Palindrome

Now we are into logic. First let me point out that the LEFT and RIGHT functions you are using are great, but they are going to give you the number of characters you pass in from the requested direction. So let's say you passed in the word "test". On the first pass you are going to get this (removing variables):

LEFT('test',1) = RIGHT('test',4)
    t          =      test

LEFT('test',2) = RIGHT('test',3)
    te         =      est

Obviously that isn't what you expected. You would really want to use substring instead. Substring lets you pass in not only the starting point but the length. So you would get:

SUBSTRING('test',1,1) = SUBSTRING('test',4,1)
         t            =         t

SUBSTRING('test',2,1) = SUBSTRING('test',3,1)
         e            =         s

Next you are incrementing the variables you use in your loop only in one condition of the IF statement. Pull the variable incrementing out of that structure entirely. That is going to require an additional BEGIN .. END block, but I do get to remove the other one.

        WHILE @StringLength - @n > 1 
            BEGIN
                IF SUBSTRING(@String,@n,1) = SUBSTRING(@String, @StringLength,1)
                    SET @Palindrome = 1 
                ELSE 
                    SET @Palindrome = 0

                SET @n = @n + 1
                SET @StringLength = @StringLength - 1
            END

You need to change your WHILE condition to allow for the last test.

        WHILE @StringLength > @n 

And last but not least, the way it stands now we don't test the last character if there are an odd number of characters. For example with 'ana' the n isn't tested. That's fine but it does me we need to account for a single letter word (if you want it to count as a positive that is). So we can do that by setting the value up front.

And now we finally have:

CREATE FUNCTION Palindrome (@String  varchar(255)) 
RETURNS Binary
AS

    BEGIN
        DECLARE @StringLength  Int
            , @n Int
            , @Palindrome binary

        SET @n = 1
        SET @StringLength = Len(@String)
        SET @Palindrome = 1

        WHILE @StringLength > @n 
            BEGIN
                IF SUBSTRING(@String,@n,1) = SUBSTRING(@String, @StringLength,1)
                    SET @Palindrome = 1 
                ELSE 
                    SET @Palindrome = 0

                SET @n = @n + 1
                SET @StringLength = @StringLength - 1
            END
        RETURN @Palindrome
    END

One last comment. I'm a big fan of formatting in general. It can really help you to see how your code works and help to point out possible mistakes.

Edit

As Sphinxxx mentioned we still have a flaw in our logic. Once we hit the ELSE and set @Palindrome to 0 there is no point in continuing. In fact at that point we could just RETURN.

                IF SUBSTRING(@String,@n,1) = SUBSTRING(@String, @StringLength,1)
                    SET @Palindrome = 1 
                ELSE 
                    RETURN 0

Given that we are now only using @Palindrome for "it's still possible this is a palindrome" there is really no point in having it. We can get rid of the variable and switch our logic to short circuit on failure (the RETURN 0) and RETURN 1 (a positive response) only if it makes it all the way through the loop. You'll notice this actually simplifies our logic somewhat.

CREATE FUNCTION Palindrome (@String  varchar(255)) 
RETURNS Binary
AS

    BEGIN
        DECLARE @StringLength  Int
            , @n Int

        SET @n = 1
        SET @StringLength = Len(@String)

        WHILE @StringLength > @n 
            BEGIN
                IF SUBSTRING(@String,@n,1) <> SUBSTRING(@String, @StringLength,1)
                    RETURN 0

                SET @n = @n + 1
                SET @StringLength = @StringLength - 1
            END
        RETURN 1
    END

Answer 2

If you are using SQL Server you can use the REVERSE() function to check?

SELECT CASE WHEN @string = REVERSE(@String) THEN 1 ELSE 0 END AS Palindrome;

---

Including Martin Smith's comment, if you are on SQL Server 2012+ you can use the IIF() function:

SELECT IIF(@string = REVERSE(@String),1,0) AS Palindrome;

Answer 3

You could also use a Numbers table approach.

If you don't already have an auxiliary numbers table you can create one as follows. This is populated with a million rows and so will be good for string lengths up to 2 million characters.

CREATE TABLE dbo.Numbers (number int PRIMARY KEY);

INSERT INTO dbo.Numbers
            (number)
SELECT TOP 1000000 ROW_NUMBER() OVER (ORDER BY @@SPID)
FROM   master..spt_values v1,
       master..spt_values v2 

The below compares each character on the left with its corresponding partner on the right, and if any discrepancies are found can short circuit and return 0. If the string is an odd length the middle character is not checked as this won't alter the result.

DECLARE @Candidate VARCHAR(MAX) = 'aibohphobia'; /*the irrational fear of palindromes.*/

SET @Candidate = LTRIM(RTRIM(@Candidate)); /*Ignoring any leading or trailing spaces. 
                      Could use `DATALENGTH` instead of `LEN` if these are significant*/

SELECT CASE
         WHEN EXISTS (SELECT *
                      FROM   dbo.Numbers
                      WHERE  number <= LEN(@Candidate) / 2
                             AND SUBSTRING(@Candidate, number, 1) 
                              <> SUBSTRING(@Candidate, 1 + LEN(@Candidate) - number, 1))
           THEN 0
         ELSE 1
       END AS IsPalindrome 

If you're not sure how it works you can see from the below

DECLARE @Candidate VARCHAR(MAX) = 'this is not a palindrome';

SELECT SUBSTRING(@Candidate, number, 1)                       AS [Left],
       SUBSTRING(@Candidate, 1 + LEN(@Candidate) - number, 1) AS [Right]
FROM   dbo.Numbers
WHERE  number <= LEN(@Candidate) / 2; 

This is basically the same algorithm as described in the question, but done in a set based way rather than iterative procedural code.

Answer 4

The REVERSE() method "improved", i.e. reversing only half of the string:

SELECT CASE WHEN RIGHT(@string, LEN(@string)/2) 
                 = REVERSE(LEFT(@string, LEN(@string)/2)) 
            THEN 1 ELSE 0 END AS Palindrome;

I don't expect anything weird to happen if the string has an odd number of characters; the middle character doesn't have to be checked.

---

A remark was raised by @hvd that this might not handle surrogate pairs correctly in all collations.

@srutzky commented that it handles Supplementary Characters / Surrogate Pairs in the same manner as the REVERSE() method, in that they only work properly when the current database's default Collation ends in _SC.

Answer 5

Without using REVERSE, which is what immediately comes to mind, but still using a function¹; I would construct something like the following.

This part simply removed the existing function, if it already exists:

IF OBJECT_ID('dbo.IsPalindrome') IS NOT NULL
DROP FUNCTION dbo.IsPalindrome;
GO

This is the function itself:

CREATE FUNCTION dbo.IsPalindrome
(
    @Word NVARCHAR(500)
) 
RETURNS BIT
AS
BEGIN
    DECLARE @IsPalindrome BIT;
    DECLARE @LeftChunk NVARCHAR(250);
    DECLARE @RightChunk NVARCHAR(250);
    DECLARE @StrLen INT;
    DECLARE @Pos INT;

    SET @RightChunk = '';
    SET @IsPalindrome = 0;
    SET @StrLen = LEN(@Word) / 2;
    IF @StrLen % 2 = 1 SET @StrLen = @StrLen - 1;
    SET @Pos = LEN(@Word);
    SET @LeftChunk = LEFT(@Word, @StrLen);

    WHILE @Pos > (LEN(@Word) - @StrLen)
    BEGIN
        SET @RightChunk = @RightChunk + SUBSTRING(@Word, @Pos, 1)
        SET @Pos = @Pos - 1;
    END

    IF @LeftChunk = @RightChunk SET @IsPalindrome = 1;
    RETURN (@IsPalindrome);
END
GO

Here, we test the function:

IF dbo.IsPalindrome('This is a word') = 1 
    PRINT 'YES'
ELSE
    PRINT 'NO';

IF dbo.IsPalindrome('tattarrattat') = 1 
    PRINT 'YES'
ELSE
    PRINT 'NO';

This compares the first half of the word with the reverse of the last half of the word (without using the REVERSE function). This code properly handles both odd and even length words. Instead of looping through the entire word, we simply get the LEFT of the first half of the word, then loop through the last half of the word to get the reversed portion of the right half. If the word is an odd-length, we skip the middle letter, since by definition it will be the same for both "halves".

---

^{1 - functions can be very slow!}

Answer 6

This is an inline TVF-friendly version of Martin Smith's set-based solution, additionally decorated with a couple of superfluous enhancements:

WITH Nums AS
(
  SELECT
    N = number
  FROM
    dbo.Numbers WITH(FORCESEEK) /*Requires a suitably indexed numbers table*/
)
SELECT
  IsPalindrome =
    CASE
      WHEN EXISTS
      (
        SELECT *
        FROM Nums
        WHERE N <= L / 2
          AND SUBSTRING(S, N, 1) <> SUBSTRING(S, 1 + L - N, 1)
      )
      THEN 0
      ELSE 1
    END
FROM
  (SELECT LTRIM(RTRIM(@Candidate)), LEN(@Candidate)) AS v (S, L)
;

Answer 7

Without using REVERSE... It's always fun to use a recursive solution ;) (I did mine in SQL Server 2012, earlier versions might have limitations on recursion)

create function dbo.IsPalindrome (@s varchar(max)) returns bit
as
begin
    return case when left(@s,1) = right(@s,1) then case when len(@s) < 3 then 1 else dbo.IsPalindrome(substring(@s,2,len(@s)-2)) end else 0 end;
end;
GO

select dbo.IsPalindrome('a')
1
select dbo.IsPalindrome('ab')
0
select dbo.IsPalindrome('bab')
1
select dbo.IsPalindrome('gohangasalamiimalasagnahog')
1

Answer 8

Just for fun, here's a SQL Server 2016 Scalar User-Defined function with the In-Memory OLTP feature:

ALTER FUNCTION dbo.IsPalindrome2 ( @inputString NVARCHAR(500) )
RETURNS BIT
WITH NATIVE_COMPILATION, SCHEMABINDING
AS
BEGIN ATOMIC WITH (TRANSACTION ISOLATION LEVEL = SNAPSHOT, LANGUAGE = N'English')

    DECLARE @i INT = 1, @j INT = LEN(@inputString)

    WHILE @i < @j
    BEGIN
        IF SUBSTRING( @inputString, @i, 1 ) != SUBSTRING( @inputString, @j, 1 )
        BEGIN
            RETURN(0)
        END
        ELSE
            SELECT @i+=1, @j-=1

    END

    RETURN(1)

END
GO

Answer 9

A major issue you're going to run into is that with any value greater than 1, LEFT or RIGHT will return multiple characters, not the character at that position. If you wanted to keep with this method of test, a really simple way to modify it would be

RIGHT(LEFT(String,@n),1)=LEFT(RIGHT(String, @StringLength),1)

This will always grab the rightmost character of the left string and the leftmost character of the right string.

Perhaps a less roundabout way to check this, though, would be to use SUBSTRING:

SUBSTRING(String, @n, 1) = SUBSTRING(String, ((LEN(String) - @n) + 1), 1)

Note that SUBSTRING is 1-indexed, hence the + 1 in ((LEN(String) - @n) + 1).