Teste se uma string é um palíndromo usando T-SQL

24

Eu sou iniciante em T-SQL. Eu quero decidir se uma string de entrada é um palíndromo, com output = 0 se não for e output = 1 se for. Ainda estou descobrindo a sintaxe. Eu nem estou recebendo uma mensagem de erro. Estou procurando soluções diferentes e algum feedback, para obter um melhor entendimento e conhecimento de como o T-SQL funciona, para me aperfeiçoar - ainda sou estudante.

A idéia principal, a meu ver, é comparar os caracteres mais à esquerda e à direita, verificar a igualdade e comparar o segundo caractere da esquerda com o 2º do último, etc. Fazemos um loop: se os caracteres forem iguais, continuaremos. Se chegamos ao fim, produzimos 1, se não, produzimos 0.

Você poderia criticar:

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

Acho que estou no caminho certo, mas ainda estou longe. Alguma ideia?

MSIS
fonte
LTRIM(RTRIM(...))espaço em branco?
WernerCD

Respostas:

60

Se você estiver usando o SQL Server, poderá usar a função REVERSE () para verificar?

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

Incluindo o comentário de Martin Smith, se você estiver no SQL Server 2012+, poderá usar a função IIF () :

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

Como existe um número razoável de soluções, eu irei à parte "crítica" da sua pergunta. Algumas notas: Corrigi alguns erros de digitação e observei onde fiz. Se eu estiver errado sobre o erro de digitação, mencione-o nos comentários e explico o que está acontecendo. Vou apontar várias coisas que você já deve saber, então, por favor, não se ofenda se eu soubesse. Alguns comentários podem parecer exigentes, mas eu não sei onde você está em sua jornada, portanto, suponha que você está apenas começando.

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

SEMPRE inclua o comprimento com a charou varchardefinition. Aaron Bertrand fala sobre isso em profundidade aqui . Ele está falando, varcharmas o mesmo vale para char. Eu usaria um varchar(255)para isso se você quiser apenas cordas relativamente curtas ou talvez uma varchar(8000)para cordas maiores ou até mesmo varchar(max). Varcharé para cadeias de comprimento variável charé apenas para cadeias fixas. Como você não tem certeza do comprimento da cadeia que está sendo passada em uso varchar. Também é binarynão bin.

Em seguida, você não precisa colocar todas essas variáveis ​​como parâmetros. Declare-os dentro do seu código. Coloque apenas algo na lista de parâmetros se você planeja passá-lo para dentro ou para fora. (Você verá como isso fica no final.) Além disso, você tem @StringLeftLength, mas nunca o usa. Então, eu não vou declarar isso.

A próxima coisa que vou fazer é reformatar um pouco para deixar algumas coisas óbvias.

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

Se você olhar para o jeito que eu fiz o recuo, você perceberá que eu tenho isso:

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

Isso ocorre porque comandos como WHILEe IFafetam apenas a primeira linha de código após eles. Você precisa usar um BEGIN .. ENDbloco se desejar vários comandos. Então, corrigindo o que temos:

    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

Você notará que eu adicionei apenas um BEGIN .. ENDbloco no IF. Isso IFocorre porque, embora a declaração tenha várias linhas (e até contenha vários comandos), ainda é uma única declaração (cobrindo tudo o que é executado nas partes IFe nas ELSEpartes da declaração).

Em seguida, você receberá um erro após os dois RETURNs. Você pode retornar uma variável OU um literal. Você não pode definir a variável e retorná-la ao mesmo tempo.

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

    RETURN @Palindrome

Agora estamos na lógica. Primeiro, deixe-me salientar que as funções LEFTe que RIGHTvocê está usando são ótimas, mas elas fornecem o número de caracteres que você passa da direção solicitada. Então, digamos que você passou na palavra "teste". Na primeira passagem, você obterá isso (removendo variáveis):

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

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

Obviamente, isso não é o que você esperava. Você realmente gostaria de usar substring. Substring permite passar não apenas o ponto inicial, mas também o comprimento. Então você obteria:

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

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

Em seguida, você está incrementando as variáveis ​​que você usa em seu loop apenas em uma condição da instrução SE. Puxe a variável incrementada para fora dessa estrutura completamente. Isso vai exigir um BEGIN .. ENDbloco adicional , mas eu consigo remover o outro.

        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

Você precisa alterar sua WHILEcondição para permitir o último teste.

        WHILE @StringLength > @n 

E por último, mas não menos importante, do jeito que está agora, não testamos o último caractere se houver um número ímpar de caracteres. Por exemplo, com 'ana', o nnão é testado. Tudo bem, mas, para mim, precisamos contabilizar uma única letra (se você quiser que isso seja positivo). Então, podemos fazer isso definindo o valor antecipadamente.

E agora finalmente temos:

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

Um último comentário. Eu sou um grande fã de formatação em geral. Pode realmente ajudar você a ver como seu código funciona e ajudar a apontar possíveis erros.

Editar

Como Sphinxxx mencionou, ainda temos uma falha em nossa lógica. Quando atingimos ELSEe definimos @Palindromecomo 0, não faz sentido continuar. De fato, naquele ponto, poderíamos apenas RETURN.

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

Dado que agora estamos usando apenas @Palindromepara "ainda é possível, isso é um palíndromo", não há realmente sentido em tê-lo. Podemos nos livrar da variável e mudar nossa lógica para um curto-circuito em caso de falha (a RETURN 0) e RETURN 1(uma resposta positiva) apenas se ela passar por todo o ciclo. Você notará que isso realmente simplifica um pouco nossa lógica.

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
Kenneth Fisher
fonte
15

Você também pode usar uma abordagem de tabela do Numbers.

Se você ainda não possui uma tabela de números auxiliares, pode criar uma da seguinte maneira. Isso é preenchido com um milhão de linhas e, portanto, será bom para comprimentos de cadeia de até 2 milhões de caracteres.

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 

A seguir, compara cada caractere à esquerda com seu parceiro correspondente à direita e, se forem encontradas discrepâncias, pode causar um curto-circuito e retornar 0. Se a string tiver um comprimento ímpar, o caractere do meio não será verificado, pois isso não alterará o resultado. .

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 

Se você não tem certeza de como funciona, pode ver a seguir

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; 

insira a descrição da imagem aqui

Esse é basicamente o mesmo algoritmo descrito na pergunta, mas feito de maneira baseada em conjunto, em vez de código processual iterativo.

Martin Smith
fonte
12

O REVERSE()método "melhorou", ou seja, revertendo apenas metade da string:

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

Não espero que algo estranho aconteça se a string tiver um número ímpar de caracteres; o personagem do meio não precisa ser verificado.


Uma observação foi levantada pelo @hvd de que isso pode não lidar corretamente com pares substitutos em todos os agrupamentos.

A @srutzky comentou que lida com pares de caracteres suplementares / substitutos da mesma maneira que o REVERSE()método, na medida em que eles só funcionam corretamente quando o agrupamento padrão do banco de dados atual termina _SC.

ypercubeᵀᴹ
fonte
8

Sem usar REVERSE, é o que imediatamente vem à mente, mas ainda usando a função 1 ; Eu construiria algo como o seguinte.

Esta parte simplesmente removeu a função existente, se ela já existir:

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

Esta é a própria função:

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

Aqui, testamos a função:

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

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

Isso compara a primeira metade da palavra com o reverso da última metade da palavra (sem usar a REVERSEfunção). Esse código lida adequadamente com palavras pares e ímpares. Em vez de percorrer a palavra inteira, simplesmente obtemos a LEFTprimeira metade da palavra e, em seguida, percorremos a última metade da palavra para obter a parte invertida da metade direita. Se a palavra tiver um comprimento ímpar, pularemos a letra do meio, pois, por definição, será a mesma para as duas "metades".


1 - as funções podem ser muito lentas!

Max Vernon
fonte
6

Sem usar REVERSE ... É sempre divertido usar uma solução recursiva;) (fiz o meu no SQL Server 2012, as versões anteriores podem ter limitações de recursão)

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
Kevin Suchlicki
fonte
6

Esta é uma versão em linha compatível com TVF da solução baseada em conjuntos de Martin Smith , decorada adicionalmente com algumas melhorias supérfluas:

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)
;
Andriy M
fonte
5

Apenas por diversão, aqui está uma função definida pelo usuário escalar do SQL Server 2016 com o recurso OLTP na memória:

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
wBob
fonte
4

Um dos principais problemas que você encontrará é que, com qualquer valor maior que 1, LEFTou RIGHTretornará vários caracteres, não o personagem nessa posição. Se você quiser continuar com esse método de teste, uma maneira realmente simples de modificá-lo seria

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

Isso sempre pega o caractere mais à direita da string esquerda e o caractere mais à esquerda da string direita.

Talvez uma maneira menos indireta de verificar isso, porém, fosse usar SUBSTRING:

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

Observe que SUBSTRINGé indexado em 1, daí o + 1in ((LEN(String) - @n) + 1).

Andy
fonte