Sprawdź, czy ciąg jest palindromem przy użyciu T-SQL

24

Jestem początkującym w języku T-SQL. Chcę zdecydować, czy ciąg wejściowy jest palindromem, z wynikiem = 0, jeśli nie jest, a wyjście = 1, jeśli tak jest. Nadal zastanawiam się nad składnią. Nie dostaję nawet komunikatu o błędzie. Szukam różnych rozwiązań i informacji zwrotnych, aby lepiej zrozumieć i zrozumieć działanie T-SQL, aby stać się lepszym - wciąż jestem studentem.

Według mnie kluczową ideą jest porównanie między sobą lewej i prawej strony, sprawdzenie równości, a następnie porównanie drugiego znaku od lewej z drugim od ostatniego itd. Robimy pętlę: jeśli znaki są sobie równe, kontynuujemy. Jeśli osiągnęliśmy koniec, wyprowadzamy 1, jeśli nie, wyprowadzamy 0.

Czy mógłbyś zadowolić krytykę:

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

Myślę, że jestem na dobrej drodze, ale wciąż jestem daleko. Jakieś pomysły?

MSIS
źródło
LTRIM(RTRIM(...))Biała przestrzeń?
WernerCD

Odpowiedzi:

60

Jeśli używasz programu SQL Server, możesz użyć funkcji REVERSE () do sprawdzenia?

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

Łącznie z komentarzem Martina Smitha, jeśli korzystasz z SQL Server 2012+, możesz użyć funkcji IIF () :

SELECT IIF(@string = REVERSE(@String),1,0) AS Palindrome;
Shaneis
źródło
17

Ponieważ istnieje spora liczba rozwiązań, przejdę do części „krytyki” twojego pytania. Kilka uwag: Naprawiłem kilka literówek i zauważyłem, gdzie to zrobiłem. Jeśli się mylę, że są literówką, wspomnij o tym w komentarzach, a wyjaśnię, co się dzieje. Mam zamiar wskazać kilka rzeczy, które być może już wiesz, więc proszę, nie obrażaj się, jeśli to zrobię. Niektóre komentarze mogą wydawać się wybredne, ale nie wiem, gdzie jesteś w podróży, więc musisz założyć, że dopiero zaczynasz.

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

ZAWSZE uwzględniaj długość z definicją charlub varchar. Aaron Bertrand mówi tutaj dogłębnie . Mówi, varcharale to samo dotyczy char. Użyłbym varchar(255)do tego, jeśli chcesz tylko stosunkowo krótkich łańcuchów, a może varchar(8000)dla większych, a nawet varchar(max). Varcharjest dla ciągów o zmiennej długości charjest tylko dla stałych. Ponieważ nie jesteś pewien długości przekazywanego ciągu w użyciu varchar. Także to binarynie bin.

Następnie nie musisz umieszczać wszystkich tych zmiennych jako parametrów. Zadeklaruj je w swoim kodzie. Umieść coś na liście parametrów tylko, jeśli planujesz przekazać lub wyrzucić. (Zobaczysz, jak to wygląda na końcu.) Również masz @StringLeftLength, ale nigdy go nie używaj. Więc nie zamierzam tego deklarować.

Następną rzeczą, którą zamierzam zrobić, jest ponowne sformatowanie, aby kilka rzeczy było oczywistych.

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

Jeśli spojrzysz na sposób, w jaki zrobiłem wcięcie, zauważysz, że mam to:

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

Jest tak, ponieważ polecenia takie jak WHILEi IFwpływają tylko na pierwszy wiersz kodu po nich. Musisz użyć BEGIN .. ENDbloku, jeśli chcesz mieć wiele poleceń. Naprawiając to, otrzymujemy:

    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

Zauważysz, że dodałem tylko BEGIN .. ENDblok w IF. To dlatego, mimo że IFoświadczenie jest wiele linii długo (a nawet zawiera wiele poleceń) jest jeszcze jedno sprawozdanie (obejmujące wszystko wykonywane w IFa ELSEczęściami rachunku).

Następnie pojawi się błąd po obu RETURNs. Możesz zwrócić zmienną LUB literał. Nie można ustawić zmiennej i zwrócić jej jednocześnie.

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

    RETURN @Palindrome

Teraz jesteśmy w logice. Po pierwsze, pozwól mi zaznaczyć, że funkcje LEFTi RIGHT, których używasz, są świetne, ale podadzą ci liczbę znaków przekazywanych z żądanego kierunku. Powiedzmy, że zdałeś słowo „test”. Przy pierwszym przejściu dostaniesz to (usuwanie zmiennych):

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

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

Oczywiście nie tego się spodziewałeś. Naprawdę chcesz użyć substringzamiast tego. Podciąg pozwala przekazać nie tylko punkt początkowy, ale także długość. Otrzymasz więc:

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

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

Następnie zwiększasz zmienne używane w pętli tylko w jednym warunku instrukcji IF. Całkowicie wyciągnij zmienną inkrementację z tej struktury. Będzie to wymagało dodatkowego BEGIN .. ENDbloku, ale mogę usunąć drugi.

        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

Musisz zmienić swój WHILEstan, aby umożliwić ostatni test.

        WHILE @StringLength > @n 

I na koniec, tak jak teraz, nie testujemy ostatniego znaku, jeśli liczba znaków jest nieparzysta. Na przykład z „ana” nnie jest testowany. W porządku, ale to do mnie należy, że musimy uwzględnić jedno literowe słowo (jeśli chcesz, aby było liczone jako pozytywne). Możemy to zrobić, ustawiając wartość z góry.

A teraz w końcu mamy:

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

Ostatni komentarz. Ogólnie jestem wielkim fanem formatowania. To naprawdę może ci pomóc zobaczyć, jak działa twój kod i pomóc wskazać możliwe błędy.

Edytować

Jak wspomniał Sphinxxx, nadal mamy wadę w naszej logice. Po trafieniu ELSEi ustawieniu @Palindromena 0 nie ma sensu kontynuować. W tym momencie moglibyśmy właśnie RETURN.

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

Biorąc pod uwagę, że teraz używamy tylko @Palindromedo „wciąż jest to palindrom”, naprawdę nie ma sensu go mieć. Możemy pozbyć się zmiennej i przełączyć naszą logikę na zwarcie w przypadku awarii ( RETURN 0) i RETURN 1(reakcja pozytywna) tylko wtedy, gdy przejdzie ona przez całą pętlę. Zauważysz, że to faktycznie nieco upraszcza naszą logikę.

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
źródło
15

Możesz także użyć podejścia do tabeli liczb.

Jeśli nie masz jeszcze tabeli numerów pomocniczych, możesz ją utworzyć w następujący sposób. Jest wypełniony milionem wierszy, więc będzie dobry dla ciągów o długości do 2 milionów znaków.

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 

Poniżej porównuje każdy znak po lewej stronie z odpowiadającym mu partnerem po prawej stronie, a jeśli zostaną znalezione jakiekolwiek rozbieżności, może dojść do zwarcia i zwrócenia 0. Jeśli łańcuch ma dziwną długość, środkowy znak nie jest sprawdzany, ponieważ nie zmieni to wyniku .

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 

Jeśli nie masz pewności, jak to działa, możesz zobaczyć poniżej

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; 

wprowadź opis zdjęcia tutaj

Jest to w zasadzie ten sam algorytm, jaki opisano w pytaniu, ale jest wykonywany w oparciu o zestaw, a nie iteracyjny kod proceduralny.

Martin Smith
źródło
12

REVERSE()Metoda „ulepszone”, czyli cofania tylko połowa napisu:

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

Nie oczekuję, że wydarzy się coś dziwnego, jeśli łańcuch będzie miał nieparzystą liczbę znaków; środkowy znak nie musi być sprawdzany.


@Hvd podniósł uwagę, że może to nie obsługiwać poprawnie par zastępczych we wszystkich zestawieniach.

@srutzky skomentował, że obsługuje pary znaków uzupełniających / zastępczych w taki sam sposób jak REVERSE()metodę, ponieważ działają one tylko, gdy kończy się domyślne sortowanie bieżącej bazy danych _SC.

ypercubeᵀᴹ
źródło
8

Bez użycia REVERSE, co natychmiast przychodzi na myśl, ale nadal z wykorzystaniem funkcji 1 ; Skonstruowałbym coś takiego.

Ta część po prostu usunęła istniejącą funkcję, jeśli już istnieje:

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

To jest sama funkcja:

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

Tutaj testujemy funkcję:

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

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

Porównuje to pierwszą połowę słowa z odwrotnością ostatniej połowy słowa (bez użycia REVERSEfunkcji). Ten kod poprawnie obsługuje słowa nieparzyste i parzyste. Zamiast zapętlać całe słowo, po prostu otrzymujemy LEFTpierwszą część słowa, a następnie zapętlamy ostatnią połowę słowa, aby uzyskać odwróconą część prawej połowy. Jeśli słowo ma nieparzystą długość, pomijamy środkową literę, ponieważ z definicji będzie taka sama dla obu „połówek”.


1 - funkcje mogą być bardzo wolne!

Max Vernon
źródło
6

Bez użycia REVERSE ... Zawsze fajnie jest korzystać z rozwiązania rekurencyjnego;) (zrobiłem mój w SQL Server 2012, wcześniejsze wersje mogły mieć ograniczenia rekurencji)

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
źródło
6

Jest to wbudowana, przyjazna dla TVF wersja rozwiązania Martina Smitha oparta na zestawie , dodatkowo ozdobiona kilkoma zbędnymi ulepszeniami:

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.
źródło
5

Dla zabawy, oto skalarna funkcja SQL Server 2016 zdefiniowana przez użytkownika z funkcją OLTP w pamięci:

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
źródło
4

Głównym problemem, na który natkniesz się, jest to, że o dowolnej wartości większej niż 1, LEFTlub RIGHTzwróci wiele znaków, a nie znak w tej pozycji. Jeśli chcesz pozostać przy tej metodzie testu, to naprawdę prosty sposób na jej zmodyfikowanie

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

Spowoduje to zawsze złapanie znaku znajdującego się najbardziej na prawo od lewego ciągu i znaku znajdującego się najbardziej na lewo od prawego ciągu.

Być może jednak mniej okrągłym sposobem na sprawdzenie tego byłoby użycie SUBSTRING:

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

Zauważ, że SUBSTRINGjest indeksowany 1, stąd + 1in ((LEN(String) - @n) + 1).

Andy
źródło