Testen Sie mithilfe von T-SQL, ob eine Zeichenfolge ein Palindrom ist

24

Ich bin ein Anfänger in T-SQL. Ich möchte entscheiden, ob eine Eingabezeichenfolge ein Palindrom ist, mit output = 0, wenn dies nicht der Fall ist, und output = 1, wenn dies der Fall ist. Ich finde immer noch die Syntax heraus. Ich erhalte nicht einmal eine Fehlermeldung. Ich suche nach verschiedenen Lösungen und ein paar Rückmeldungen, um besser zu verstehen und zu verstehen, wie T-SQL funktioniert, um besser darin zu werden - ich bin noch Student.

Die Schlüsselidee, wie ich es sehe, ist es, die Zeichen ganz links und ganz rechts miteinander zu vergleichen, auf Gleichheit zu prüfen und dann das zweite Zeichen von links mit dem zweitletzten zu vergleichen usw. Wir machen eine Schleife: Wenn die Zeichen gleich sind, fahren wir fort. Wenn wir das Ende erreicht haben, geben wir 1 aus, wenn nicht, geben wir 0 aus.

Würden Sie bitte kritisieren:

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

Ich glaube, ich bin auf dem richtigen Weg, aber ich bin noch weit weg. Irgendwelche Ideen?

MSIS
quelle
LTRIM(RTRIM(...))Leerzeichen?
WernerCD

Antworten:

60

Wenn Sie SQL Server verwenden, können Sie mit der Funktion REVERSE () überprüfen, ob?

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

Mit dem Kommentar von Martin Smith können Sie in SQL Server 2012+ die IIF () -Funktion verwenden:

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

Da es eine ganze Reihe von Lösungen gibt, werde ich mich mit dem "Kritik" -Teil Ihrer Frage befassen. Ein paar Anmerkungen: Ich habe einige Tippfehler behoben und festgestellt, wo ich sie gemacht habe. Wenn ich mich geirrt habe, erwähne ich es in den Kommentaren und erkläre, was los ist. Ich werde auf einige Dinge hinweisen, die Sie vielleicht bereits wissen, nehmen Sie sich also bitte keine Sorgen, wenn ich es tue. Einige Kommentare mögen wählerisch erscheinen, aber ich weiß nicht, wo Sie sich auf Ihrer Reise befinden, also müssen Sie davon ausgehen, dass Sie gerade erst anfangen.

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

Schließen Sie IMMER die Länge mit einem charoder einer varcharDefinition ein. Aaron Bertrand spricht hier ausführlich darüber . Er redet, varcharaber das gilt auch char. Ich würde dafür eine verwenden, varchar(255)wenn Sie nur relativ kurze Zeichenfolgen oder vielleicht eine varchar(8000)für größere oder sogar möchten varchar(max). Varcharist für Zeichenfolgen mit variabler Länge charnur für feste Zeichenfolgen . Da Sie nicht sicher sind, wie lange die Zeichenfolge verwendet wird varchar. Auch ist es binarynicht bin.

Als Nächstes müssen Sie nicht alle diese Variablen als Parameter angeben. Deklarieren Sie sie in Ihrem Code. Nehmen Sie etwas nur in die Parameterliste auf, wenn Sie es weitergeben möchten. (Sie werden sehen, wie dies am Ende aussieht.) Sie haben auch @StringLeftLength, verwenden es aber nie. Also werde ich es nicht erklären.

Das nächste, was ich tun werde, ist ein bisschen neu zu formatieren, um ein paar Dinge klar zu machen.

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

Wenn Sie sich die Art und Weise ansehen, wie ich die Einrückung vorgenommen habe, werden Sie feststellen, dass ich Folgendes habe:

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

Das ist , weil Befehle wie WHILEund IFnur die erste Zeile des Codes nach ihnen beeinflussen. Sie müssen einen BEGIN .. ENDBlock verwenden, wenn Sie mehrere Befehle wünschen. So fixierend, dass wir bekommen:

    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

Sie werden bemerken, dass ich nur einen BEGIN .. ENDBlock in den Ordner eingefügt habe IF. Das liegt daran, dass die IFAnweisung, obwohl sie mehrere Zeilen lang ist (und sogar mehrere Befehle enthält), immer noch eine einzelne Anweisung ist (die alles abdeckt, was in IFund in den ELSETeilen der Anweisung ausgeführt wird).

Als nächstes erhalten Sie nach beiden eine Fehlermeldung RETURNs. Sie können eine Variable ODER ein Literal zurückgeben. Sie können die Variable nicht gleichzeitig setzen und zurückgeben.

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

    RETURN @Palindrome

Jetzt sind wir in der Logik. Lassen Sie mich zunächst darauf hinweisen, dass die LEFTund RIGHTFunktionen, die Sie verwenden, großartig sind, aber Ihnen die Anzahl der Zeichen geben werden, die Sie aus der angeforderten Richtung übergeben. Angenommen, Sie haben das Wort "Test" bestanden. Beim ersten Durchgang erhalten Sie Folgendes (Entfernen von Variablen):

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

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

Offensichtlich haben Sie das nicht erwartet. Sie würden wirklich substringstattdessen verwenden möchten . Mit der Teilzeichenfolge können Sie nicht nur den Startpunkt, sondern auch die Länge eingeben. So würden Sie erhalten:

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

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

Als nächstes erhöhen Sie die Variablen, die Sie in Ihrer Schleife verwenden, nur in einer Bedingung der IF-Anweisung. Ziehen Sie die Variableninkrementierung vollständig aus dieser Struktur heraus. Das erfordert einen zusätzlichen BEGIN .. ENDBlock, aber ich muss den anderen entfernen.

        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

Sie müssen Ihren WHILEZustand ändern , um den letzten Test durchführen zu können.

        WHILE @StringLength > @n 

Und last but not least, wie es jetzt aussieht, testen wir nicht das letzte Zeichen, wenn es eine ungerade Anzahl von Zeichen gibt. Zum Beispiel mit 'ana' wird das nnicht getestet. Das ist in Ordnung, aber es tut mir leid, dass wir ein einzelnes Buchstabenwort berücksichtigen müssen (wenn Sie möchten, dass es als positiv gilt). Das können wir also tun, indem wir den Wert im Voraus festlegen.

Und jetzt haben wir endlich:

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

Ein letzter Kommentar. Ich bin ein großer Fan von Formatierung im Allgemeinen. Es kann Ihnen wirklich helfen, die Funktionsweise Ihres Codes zu erkennen und auf mögliche Fehler hinzuweisen.

Bearbeiten

Wie Sphinxxx sagte, haben wir immer noch einen Fehler in unserer Logik. Sobald wir die Taste drücken ELSEund @Palindromeauf 0 setzen , macht es keinen Sinn, fortzufahren. In der Tat konnten wir zu diesem Zeitpunkt nur RETURN.

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

Angesichts der Tatsache, dass wir jetzt nur @Palindromefür "Es ist immer noch möglich, dass dies ein Palindrom ist" verwenden, macht es keinen Sinn, es zu haben. Wir können die Variable loswerden und unsere Logik nur dann auf Kurzschluss bei Ausfall (der RETURN 0) und RETURN 1(einer positiven Reaktion) umschalten, wenn sie den gesamten Weg durch die Schleife zurücklegt. Sie werden feststellen, dass dies unsere Logik tatsächlich etwas vereinfacht.

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
quelle
15

Sie können auch einen Nummerntabellenansatz verwenden.

Wenn Sie noch keine Hilfsnummerntabelle haben, können Sie eine wie folgt erstellen. Diese ist mit einer Million Zeilen gefüllt und eignet sich daher für Zeichenfolgen mit einer Länge von bis zu 2 Millionen Zeichen.

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 

Das folgende vergleicht jedes Zeichen auf der linken Seite mit dem entsprechenden Partner auf der rechten Seite. Wenn Unstimmigkeiten festgestellt werden, kann dies zu einem Kurzschluss und der Rückgabe von 0 führen. Wenn die Zeichenfolge eine ungerade Länge hat, wird das mittlere Zeichen nicht überprüft, da dies das Ergebnis nicht verändert .

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 

Wenn Sie sich nicht sicher sind, wie es funktioniert, sehen Sie es unten

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; 

Bildbeschreibung hier eingeben

Dies ist im Grunde derselbe Algorithmus wie in der Frage beschrieben, wird jedoch auf Mengenbasis und nicht als iterativer Verfahrenscode ausgeführt.

Martin Smith
quelle
12

Die REVERSE()Methode "verbessert", dh nur die Hälfte des Strings umkehren:

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

Ich erwarte nicht, dass etwas Seltsames passiert, wenn die Zeichenfolge eine ungerade Anzahl von Zeichen enthält. Das mittlere Zeichen muss nicht angekreuzt werden.


@Hvd bemerkte, dass dies möglicherweise nicht in allen Kollatierungen mit Ersatzpaaren richtig umgehen kann.

@srutzky kommentierte, dass es Zusatzzeichen / Ersatzpaare auf die gleiche Weise wie die REVERSE()Methode behandelt, da sie nur dann ordnungsgemäß funktionieren, wenn die Standardkollatierung der aktuellen Datenbank auf endet _SC.

ypercubeᵀᴹ
quelle
8

Ohne zu benutzen REVERSE, was mir sofort einfällt, aber immer noch eine Funktion zu benutzen 1 ; Ich würde so etwas wie folgendes konstruieren.

Dieser Teil hat einfach die vorhandene Funktion entfernt, falls sie bereits vorhanden ist:

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

Dies ist die Funktion selbst:

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

Hier testen wir die Funktion:

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

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

Dies vergleicht die erste Worthälfte mit der Umkehrung der letzten Worthälfte (ohne Verwendung der REVERSEFunktion). Dieser Code behandelt sowohl ungerade als auch gerade Wörter. Anstatt das ganze Wort zu durchlaufen, erhalten wir einfach LEFTdie erste Hälfte des Wortes und dann die letzte Hälfte des Wortes, um den umgekehrten Teil der rechten Hälfte zu erhalten. Wenn das Wort eine ungerade Länge hat, überspringen wir den mittleren Buchstaben, da er per Definition für beide "Hälften" gleich ist.


1 - Funktionen können sehr langsam sein!

Max Vernon
quelle
6

Ohne Verwendung von REVERSE ... Es macht immer Spaß, eine rekursive Lösung zu verwenden;) (Ich habe meine in SQL Server 2012, frühere Versionen haben möglicherweise Einschränkungen bei der Rekursion)

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

Dies ist eine Inline-TVF-freundliche Version von Martin Smiths Set-basierter Lösung , die zusätzlich mit ein paar überflüssigen Verbesserungen ausgestattet ist:

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

Aus Spaß gibt es hier eine benutzerdefinierte SQL Server 2016-Skalarfunktion mit der In-Memory-OLTP-Funktion:

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

Ein Hauptproblem, auf das Sie stoßen werden, besteht darin, dass ein Wert größer als 1 LEFToder RIGHTmehrere Zeichen zurückgibt, nicht das Zeichen an dieser Position. Wenn Sie diese Testmethode beibehalten möchten, ist dies eine sehr einfache Möglichkeit, sie zu ändern

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

Dies wird immer das am weitesten rechts stehende Zeichen der linken Zeichenfolge und das am weitesten links stehende Zeichen der rechten Zeichenfolge erfassen.

Vielleicht wäre ein weniger umständlicher Weg, dies zu überprüfen, die Verwendung von SUBSTRING:

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

Beachten Sie, dass SUBSTRING1-indiziert ist, daher der + 1in ((LEN(String) - @n) + 1).

Andy
quelle