使用 T-SQL 测试字符串是否为回文

Question

我是 T-SQL 的初学者。我想确定输入字符串是否是回文，如果不是，则输出 = 0，如果是，则输出 = 1。我仍在弄清楚语法。我什至没有收到错误消息。我正在寻找不同的解决方案和一些反馈，以更好地理解和了解 T-SQL 的工作原理，从而变得更好——我仍然是一名学生。

在我看来，关键思想是将最左边和最右边的字符相互比较，检查是否相等，然后继续比较左边第二个字符和倒数第二个字符，依此类推。我们做一个循环：如果字符彼此相等，我们继续。如果到达终点，则输出 1，否则，输出 0。

请您批评一下：

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

我认为我在正确的轨道上，但我还有很长的路要走。有任何想法吗？

Answer 1

如果您使用的是 SQL Server，您可以使用REVERSE()函数来检查？

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

包括 Martin Smith 的评论，如果您使用的是 SQL Server 2012+，则可以使用IIF()函数：

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

Answer 2

由于有相当多的解决方案，我将使用您问题的“批评”部分。一些注意事项：我已经修正了一些错别字并记下了我所做的。如果我错误地认为他们是打字错误，请在评论中提及，我会解释发生了什么。我将指出一些你可能已经知道的事情，所以如果我这样做了，请不要冒犯。有些评论可能看起来很挑剔，但我不知道你在旅途中的哪个阶段，所以必须假设你才刚刚开始。

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

始终包括带有char或varchar定义的长度。Aaron Bertrand在这里深入讨论了它。他在谈论varchar但同样适用于char。我会用varchar(255)这个，如果你只需要较短的字符串或者一个varchar(8000)用于较大的或甚varchar(max)。 Varchar用于可变长度字符串char仅用于固定字符串。由于您不确定在 use 中传递的字符串的长度varchar。此外，它是binary不是bin。

接下来，您不需要将所有这些变量都作为参数。在您的代码中声明它们。如果您计划传入或传出某些内容，请仅将其放入参数列表中。（你会在最后看到它的样子。）你也有@StringLeftLength但从未使用过它。所以我不打算宣布它。

接下来我要做的是重新格式化一下，让一些事情变得明显。

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

如果你看看我做缩进的方式，你会注意到我有这个：

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

那是因为命令 likeWHILE并且IF只影响它们之后的第一行代码。BEGIN .. END如果需要多个命令，则必须使用块。所以修复我们得到：

    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

你会注意到我只BEGIN .. END在IF. 这是因为即使该IF语句有多行（甚至包含多个命令），它仍然是一个单独的语句（涵盖在语句中执行的所有内容IF和ELSE部分）。

接下来，您将在两个RETURNs. 您可以返回一个变量或一个文字。您不能设置变量并同时返回它。

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

    RETURN @Palindrome

现在我们进入逻辑。首先让我指出您正在使用的LEFT和RIGHT函数很棒，但是它们会为您提供从请求方向传入的字符数。因此，假设您通过了“测试”这个词。在第一遍你会得到这个（删除变量）：

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

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

显然这不是你所期望的。你真的想用它substring来代替。Substring 不仅可以让您传入起点，还可以传入长度。所以你会得到：

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

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

接下来，您只在 IF 语句的一个条件下增加您在循环中使用的变量。将变量增量完全从该结构中拉出。这将需要一个额外的BEGIN .. END块，但我确实可以删除另一个。

        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

您需要更改您的WHILE条件以进行最后一次测试。

        WHILE @StringLength > @n 

最后但并非最不重要的一点是，如果有奇数个字符，我们现在不会测试最后一个字符。例如，'ana'n没有经过测试。这很好，但我认为我们需要考虑单个字母单词（如果您希望将其视为正数的话）。所以我们可以通过预先设置值来做到这一点。

现在我们终于有了：

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

最后一个评论。总的来说，我是格式化的忠实粉丝。它确实可以帮助您了解代码的工作方式并帮助指出可能的错误。

编辑

正如 Sphinxxx 所提到的，我们的逻辑仍然存在缺陷。一旦我们点击ELSE并设置@Palindrome为 0，就没有继续下去的意义。事实上，那时我们可以只RETURN.

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

鉴于我们现在仅@Palindrome用于“这仍然可能是回文”，因此拥有它确实没有意义。只有当它一直通过循环时，我们才能摆脱变量并将我们的逻辑切换到故障（the ）和（积极响应）短路。你会注意到这实际上在某种程度上简化了我们的逻辑。RETURN 0RETURN 1

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 3

您还可以使用 Numbers 表格方法。

如果您还没有辅助数字表，您可以按如下方式创建一个。这填充了 100 万行，因此适用于长达 200 万个字符的字符串。

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 

下面将左边的每个字符与其右边的对应伙伴进行比较，如果发现任何差异，可以短路并返回 0。如果字符串是奇数长度，则不检查中间字符，因为这不会改变结果.

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 

如果你不确定它是如何工作的，你可以从下面看到

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; 

这与问题中描述的算法基本相同，但以基于集合的方式而不是迭代过程代码完成。

Answer 4

该REVERSE()方法“改良”，即反转字符串的只有一半：

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

如果字符串有奇数个字符，我不希望发生任何奇怪的事情；不需要检查中间字符。

@hvd 提出了一个评论，即这可能无法在所有排序规则中正确处理代理对。

@srutzky 评论说它以与REVERSE()方法相同的方式处理补充字符/代理对，因为它们仅在当前数据库的默认排序规则以_SC.

Answer 5

没有 using REVERSE，这是立即想到的，但仍然使用函数¹；我会构建类似下面的东西。

这部分只是删除了现有的功能，如果它已经存在：

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

这是函数本身：

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

在这里，我们测试一下函数：

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

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

这将单词的前半部分与单词的后半部分的反向进行比较（不使用该REVERSE函数）。此代码正确处理奇数和偶数长度的单词。我们不是遍历整个单词，而是简单地获取单词LEFT的前半部分，然后遍历单词的后半部分以获取右半部分的反向部分。如果单词是奇数长度，我们跳过中间的字母，因为根据定义，两个“半”都是一样的。

^{1 - 功能可能很慢！}

Answer 6

不使用 REVERSE ......使用递归解决方案总是很有趣;)（我在 SQL Server 2012 中做了我的，早期版本可能对递归有限制）

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 7

这是Martin Smith 基于集合的解决方案的内联 TVF 友好版本，另外还装饰了一些多余的增强功能：

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 8

只是为了好玩，这里有一个具有内存中 OLTP 功能的 SQL Server 2016 标量用户定义函数：

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