Prueba si una cadena es un palíndromo usando T-SQL

24

Soy un principiante en T-SQL. Quiero decidir si una cadena de entrada es un palíndromo, con salida = 0 si no lo es y salida = 1 si lo es. Todavía estoy descubriendo la sintaxis. Ni siquiera estoy recibiendo un mensaje de error. Estoy buscando diferentes soluciones y algunos comentarios, para obtener una mejor comprensión y conocimiento de cómo funciona T-SQL, para mejorar en eso. Todavía soy un estudiante.

La idea clave, tal como la veo, es comparar los caracteres más a la izquierda y a la derecha entre sí, verificar la igualdad, luego comparar el segundo carácter de la izquierda con el segundo-del último, etc. Hacemos un bucle: si los personajes son iguales entre sí, continuamos. Si llegamos al final, sacamos 1, si no, sacamos 0.

¿Podría por favor 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

Creo que estoy en el camino correcto, pero todavía estoy muy lejos. ¿Algunas ideas?

MSIS
fuente
LTRIM(RTRIM(...))espacio en blanco?
WernerCD

Respuestas:

60

Si está utilizando SQL Server, ¿puede usar la función REVERSE () para verificar?

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

Incluyendo el comentario de Martin Smith, si está en SQL Server 2012+ puede usar la función IIF () :

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

Como hay una buena cantidad de soluciones, voy a ir con la parte de "crítica" de su pregunta. Un par de notas: he corregido algunos errores tipográficos y anotado dónde lo hice. Si me equivoco acerca de que sean un error tipográfico, menciónelo en los comentarios y explicaré lo que está sucediendo. Voy a señalar varias cosas que quizás ya sepas, así que no te ofendas si lo supiera. Algunos comentarios pueden parecer exigentes, pero no sé dónde se encuentra en su viaje, así que debo asumir que recién está comenzando.

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

SIEMPRE incluya la longitud con una charo varchardefinición. Aaron Bertrand habla en profundidad aquí . Él está hablando varcharpero lo mismo ocurre char. Usaría un varchar(255)para esto si solo desea cadenas relativamente cortas o tal vez un varchar(8000)para las más grandes o incluso varchar(max). Varchares para cadenas de longitud variablechar es solo para fijas. Dado que no está seguro de la longitud de la cadena que se pasa en uso varchar. También es binarynobin .

A continuación, no necesita poner todas esas variables como parámetros. Declararlos dentro de su código. Solo ponga algo en la lista de parámetros si planea pasarlo dentro o fuera. (Verá cómo se ve esto al final). También tiene @StringLeftLength pero nunca lo usa. Entonces no lo voy a declarar.

Lo siguiente que voy a hacer es volver a formatear un poco para que algunas cosas sean obvias.

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

Si observa la forma en que hice la sangría, notará que tengo esto:

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

Esto se debe a que los comandos como WHILEy IFsolo afectan la primera línea de código después de ellos. Tienes que usar un BEGIN .. ENDbloque si quieres múltiples comandos. Entonces arreglando eso obtenemos:

    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

Notarás que solo agregué un BEGIN .. ENDbloque en el IF. Esto se debe a que aunque la IFdeclaración tiene varias líneas de largo (e incluso contiene múltiples comandos), sigue siendo una sola declaración (que cubre todo lo realizado en el IFy elELSE partes de la declaración).

A continuación, recibirá un error después de ambos RETURNs. Puede devolver una variable O un literal. No puede establecer la variable y devolverla al mismo tiempo.

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

    RETURN @Palindrome

Ahora estamos en la lógica. Primero permítanme señalar que las funciones LEFTy RIGHTque está utilizando son excelentes, pero le darán la cantidad de caracteres que pasa desde la dirección solicitada. Digamos que aprobaste la palabra "prueba". En la primera pasada obtendrá esto (eliminando variables):

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

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

Obviamente eso no es lo que esperabas. Realmente querrás usar substringen su lugar. La subcadena le permite pasar no solo el punto de partida sino también la longitud. Entonces obtendrías:

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

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

A continuación, está incrementando las variables que usa en su ciclo solo en una condición de la instrucción IF. Extraiga la variable incremental de esa estructura por completo. Eso requerirá un BEGIN .. ENDbloqueo adicional , pero puedo eliminar el otro.

        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

Necesita cambiar su WHILEcondición para permitir la última prueba.

        WHILE @StringLength > @n 

Y por último, pero no menos importante, tal como está ahora, no probamos el último carácter si hay un número impar de caracteres. Por ejemplo con 'ana' eln no se prueba. Eso está bien, pero me hace falta que tengamos en cuenta una palabra de una sola letra (si quieres que cuente como algo positivo). Entonces podemos hacerlo estableciendo el valor por adelantado.

Y ahora finalmente tenemos:

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

Un ultimo comentario. Soy un gran fanático del formato en general. Realmente puede ayudarlo a ver cómo funciona su código y ayudarlo a señalar posibles errores.

Editar

Como mencionó Sphinxxx, todavía tenemos una falla en nuestra lógica. Una vez que tocamos ELSEy establecemos @Palindromeen 0, no tiene sentido continuar. De hecho, en ese momento podríamos simplemente RETURN.

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

Dado que ahora solo estamos usando @Palindromepara "todavía es posible que esto sea un palíndromo", realmente no tiene sentido tenerlo. Podemos deshacernos de la variable y cambiar nuestra lógica a cortocircuito en caso de falla (la RETURN 0) y RETURN 1(una respuesta positiva) solo si logra pasar por todo el bucle. Notarás que esto realmente simplifica un poco nuestra 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
fuente
15

También podría usar un enfoque de tabla de números.

Si aún no tiene una tabla de números auxiliares, puede crear una de la siguiente manera. Esto se completa con un millón de filas y, por lo tanto, será bueno para longitudes de cadena de hasta 2 millones 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 continuación, se compara cada carácter de la izquierda con su correspondiente compañero a la derecha, y si se encuentra alguna discrepancia puede provocar un cortocircuito y devolver 0. Si la cadena tiene una longitud impar, el carácter del medio no se verifica, ya que esto no alterará el 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 

Si no está seguro de cómo funciona, puede ver a continuación

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; 

ingrese la descripción de la imagen aquí

Este es básicamente el mismo algoritmo que se describe en la pregunta, pero se realiza de una manera basada en un conjunto en lugar de un código de procedimiento iterativo.

Martin Smith
fuente
12

El REVERSE()método "mejoró", es decir, invirtió solo la mitad de la cadena:

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

No espero que suceda nada extraño si la cadena tiene un número impar de caracteres; el carácter del medio no tiene que ser verificado.


@Hvd hizo una observación de que esto podría no manejar pares sustitutos correctamente en todas las intercalaciones.

@srutzky comentó que maneja los caracteres suplementarios / pares sustitutos de la misma manera que el REVERSE()método, en el sentido de que solo funcionan correctamente cuando termina la clasificación predeterminada de la base de datos actual _SC.

ypercubeᵀᴹ
fuente
8

Sin usar REVERSE, que es lo que viene inmediatamente a la mente, pero aún usando una función 1 ; Construiría algo como lo siguiente.

Esta parte simplemente eliminó la función existente, si ya existe:

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

Esta es la función misma:

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

Aquí, probamos la función:

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

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

Esto compara la primera mitad de la palabra con el reverso de la última mitad de la palabra (sin usar la REVERSEfunción). Este código maneja correctamente las palabras de longitud par e impar. En lugar de recorrer toda la palabra, simplemente obtenemos la LEFTprimera mitad de la palabra, luego recorremos la última mitad de la palabra para obtener la parte invertida de la mitad derecha. Si la palabra tiene una longitud impar, omitimos la letra del medio, ya que, por definición, será la misma para ambas "mitades".


1 - ¡las funciones pueden ser muy lentas!

Max Vernon
fuente
6

Sin usar REVERSE ... Siempre es divertido usar una solución recursiva;) (hice la mía en SQL Server 2012, las versiones anteriores pueden tener limitaciones en la recursividad)

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
fuente
6

Esta es una versión en línea compatible con TVF de la solución basada en sets de Martin Smith , decorada adicionalmente con un par de mejoras superfluas:

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
fuente
5

Solo por diversión, aquí hay una función definida por el usuario escalar de SQL Server 2016 con la función OLTP en memoria:

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
fuente
4

Un problema importante con el que se encontrará es que con cualquier valor mayor que 1, LEFTo RIGHTdevolverá varios caracteres, no el carácter en esa posición. Si quisieras seguir con este método de prueba, una forma muy simple de modificarlo sería

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

Esto siempre tomará el carácter más a la derecha de la cadena izquierda y el carácter más a la izquierda de la cadena derecha.

Sin embargo, quizás una forma menos indirecta de verificar esto sería usar SUBSTRING:

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

Tenga en cuenta que SUBSTRINGestá indexado en 1, de ahí el + 1in ((LEN(String) - @n) + 1).

Andy
fuente