Tester si une chaîne est un palindrome à l'aide de T-SQL

24

Je suis débutant en T-SQL. Je veux décider si une chaîne d'entrée est un palindrome, avec sortie = 0 si ce n'est pas et sortie = 1 si c'est le cas. Je suis toujours en train de comprendre la syntaxe. Je ne reçois même pas de message d'erreur. Je suis à la recherche de différentes solutions et de quelques retours d'expérience, afin de mieux comprendre et connaître le fonctionnement de T-SQL, de m'améliorer - je suis encore étudiant.

L'idée clé, à mon avis, est de comparer les caractères les plus à gauche et à droite les uns aux autres, de vérifier l'égalité, puis de comparer le deuxième caractère de gauche avec le deuxième du dernier, etc. Nous faisons une boucle: si les caractères sont égaux les uns aux autres, nous continuons. Si nous avons atteint la fin, nous sortons 1, sinon, nous sortons 0.

Pourriez-vous critiquer:

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

Je pense que je suis sur la bonne voie, mais je suis encore loin. Des idées?

MSIS
la source
LTRIM(RTRIM(...))espace blanc?
WernerCD

Réponses:

60

Si vous utilisez SQL Server, vous pouvez utiliser la fonction REVERSE () pour vérifier?

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

Y compris le commentaire de Martin Smith, si vous êtes sur SQL Server 2012+, vous pouvez utiliser la fonction IIF () :

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

Puisqu'il existe un bon nombre de solutions, je vais suivre la partie «critique» de votre question. Quelques notes: j'ai corrigé quelques fautes de frappe et noté où je l'ai fait. Si je me trompe sur le fait qu'il s'agit d'une faute de frappe, mentionnez-le dans les commentaires et je vous expliquerai ce qui se passe. Je vais souligner plusieurs choses que vous savez peut-être déjà, alors ne vous en offrez pas si je le faisais. Certains commentaires peuvent sembler difficiles, mais je ne sais pas où vous en êtes dans votre voyage, alors supposez que vous débutez.

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

TOUJOURS inclure la longueur avec une définition charou varchar. Aaron Bertrand parle en détail ici . Il parle varcharmais il en va de même char. J'utiliserais un varchar(255)pour cela si vous ne voulez que des cordes relativement courtes ou peut-être un varchar(8000)pour les plus grandes ou même varchar(max). Varcharest pour les chaînes de longueur variable charest uniquement pour les chaînes fixes. Puisque vous n'êtes pas sûr de la longueur de la chaîne transmise en cours d'utilisation varchar. Ce n'est binarypas non plus bin.

Ensuite, vous n'avez pas besoin de mettre toutes ces variables en tant que paramètres. Déclarez-les dans votre code. Ne mettez quelque chose dans la liste des paramètres que si vous prévoyez de le faire entrer ou sortir. (Vous verrez à quoi cela ressemble à la fin.) Vous avez également @StringLeftLength mais ne l'utilisez jamais. Je ne vais donc pas le déclarer.

La prochaine chose que je vais faire est de reformater un peu pour rendre certaines choses évidentes.

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 vous regardez la façon dont j'ai fait l'indentation, vous remarquerez que j'ai ceci:

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

En effet, les commandes comme WHILEet IFn'affectent que la première ligne de code après elles. Vous devez utiliser un BEGIN .. ENDbloc si vous voulez plusieurs commandes. Ainsi, nous obtenons:

    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

Vous remarquerez que je n'ai ajouté qu'un BEGIN .. ENDbloc dans le IF. En effet, même si l' IFinstruction est longue de plusieurs lignes (et contient même plusieurs commandes), il s'agit toujours d'une seule instruction (couvrant tout ce qui est effectué dans IFet les ELSEparties de l'instruction).

Ensuite, vous obtiendrez une erreur après les deux RETURNs. Vous pouvez renvoyer une variable OU un littéral. Vous ne pouvez pas définir la variable et la renvoyer en même temps.

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

    RETURN @Palindrome

Maintenant, nous sommes dans la logique. Permettez-moi d'abord de souligner que les fonctions LEFTet que RIGHTvous utilisez sont excellentes, mais elles vous donneront le nombre de caractères que vous transmettez dans la direction demandée. Supposons donc que vous ayez réussi le mot "test". Lors de la première passe, vous obtiendrez ceci (suppression des variables):

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

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

Évidemment, ce n'est pas ce que vous attendiez. Vous voudriez vraiment utiliser à la substringplace. La sous-chaîne vous permet de passer non seulement le point de départ mais la longueur. Vous obtiendrez donc:

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

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

Ensuite, vous incrémentez les variables que vous utilisez dans votre boucle uniquement dans une condition de l'instruction IF. Retirez complètement la variable incrémentée de cette structure. Cela va nécessiter un BEGIN .. ENDbloc supplémentaire , mais j'arrive à supprimer l'autre.

        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

Vous devez changer votre WHILEcondition pour permettre le dernier test.

        WHILE @StringLength > @n 

Et enfin et surtout, dans l'état actuel des choses, nous ne testons pas le dernier caractère s'il y a un nombre impair de caractères. Par exemple avec 'ana' le nn'est pas testé. C'est bien, mais il me faut nous devons tenir compte d'un mot d'une seule lettre (si vous voulez qu'il compte comme un positif qui est). Nous pouvons donc le faire en définissant la valeur à l'avance.

Et maintenant, nous avons enfin:

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 dernier commentaire. Je suis un grand fan du formatage en général. Cela peut vraiment vous aider à voir comment fonctionne votre code et à signaler d'éventuelles erreurs.

modifier

Comme Sphinxxx l'a mentionné, nous avons encore un défaut dans notre logique. Une fois que nous avons touché le ELSEet mis @Palindromeà 0, il est inutile de continuer. En fait, à ce stade, nous pourrions juste RETURN.

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

Étant donné que nous n'utilisons maintenant que @Palindromepour "il est toujours possible que ce soit un palindrome", il n'y a vraiment aucun intérêt à l'avoir. Nous pouvons nous débarrasser de la variable et commuter notre logique en court-circuit en cas d'échec (le RETURN 0) et RETURN 1(une réponse positive) uniquement si cela se fait tout au long de la boucle. Vous remarquerez que cela simplifie quelque peu notre logique.

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
la source
15

Vous pouvez également utiliser une approche de table de nombres.

Si vous ne disposez pas déjà d'une table de numéros auxiliaires, vous pouvez en créer une comme suit. Celui-ci est rempli d'un million de lignes et convient donc aux longueurs de chaîne jusqu'à 2 millions de caractères.

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 

Ce qui suit compare chaque caractère à gauche avec son partenaire correspondant à droite, et si des divergences sont trouvées peuvent court-circuiter et retourner 0. Si la chaîne est d'une longueur impaire, le caractère du milieu n'est pas vérifié car cela ne changera pas le résultat .

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 vous ne savez pas comment cela fonctionne, vous pouvez le voir ci-dessous

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; 

entrez la description de l'image ici

Il s'agit essentiellement du même algorithme que celui décrit dans la question, mais fait d'une manière basée sur un ensemble plutôt que d'un code procédural itératif.

Martin Smith
la source
12

La REVERSE()méthode "améliorée", c'est-à-dire inversant seulement la moitié de la chaîne:

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

Je ne m'attends pas à ce que quelque chose d'étrange se produise si la chaîne a un nombre impair de caractères; le caractère du milieu n'a pas à être vérifié.


@Hvd a fait remarquer que cela pourrait ne pas gérer correctement les paires de substitution dans tous les classements.

@srutzky a commenté qu'il gère les caractères supplémentaires / paires de substitution de la même manière que la REVERSE()méthode, en ce sens qu'ils ne fonctionnent correctement que lorsque le classement par défaut de la base de données actuelle se termine _SC.

ypercubeᵀᴹ
la source
8

Sans utiliser REVERSE, c'est ce qui me vient immédiatement à l'esprit, mais en utilisant toujours une fonction 1 ; Je construirais quelque chose comme ce qui suit.

Cette partie a simplement supprimé la fonction existante, si elle existe déjà:

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

C'est la fonction elle-même:

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

Ici, nous testons la fonction:

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

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

Ceci compare la première moitié du mot avec l'inverse de la dernière moitié du mot (sans utiliser la REVERSEfonction). Ce code gère correctement les mots de longueur paire et impaire. Au lieu de parcourir tout le mot, nous obtenons simplement LEFTla première moitié du mot, puis parcourons la dernière moitié du mot pour obtenir la partie inversée de la moitié droite. Si le mot est d'une longueur impaire, nous sautons la lettre du milieu, car par définition, ce sera le même pour les deux "moitiés".


1 - les fonctions peuvent être très lentes!

Max Vernon
la source
6

Sans utiliser REVERSE ... C'est toujours amusant d'utiliser une solution récursive;) (J'ai fait le mien dans SQL Server 2012, les versions antérieures peuvent avoir des limites sur la récursivité)

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
la source
6

Il s'agit d'une version en ligne compatible TVF de la solution basée sur les décors de Martin Smith , en plus décorée de quelques améliorations superflues:

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
la source
5

Juste pour le plaisir, voici une fonction définie par l'utilisateur Scalar SQL Server 2016 avec la fonctionnalité OLTP en mémoire:

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
la source
4

Un problème majeur que vous allez rencontrer est qu'avec une valeur supérieure à 1, LEFT ou RIGHTrenverra plusieurs caractères, pas le caractère à cette position. Si vous vouliez continuer avec cette méthode de test, un moyen très simple de la modifier serait

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

Cela saisira toujours le caractère le plus à droite de la chaîne de gauche et le caractère le plus à gauche de la chaîne de droite.

Peut-être qu'un moyen moins détourné de vérifier cela serait d'utiliser SUBSTRING :

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

Notez qu'il SUBSTRINGest indexé 1, d'où le + 1in ((LEN(String) - @n) + 1).

Andy
la source