Palindrom w C# — sprawdzanie krok po kroku

Czego szuka rekruter: normalizacja wejścia, porównanie dwóch wskaźników, obsługa Unicode
Poziom: Junior

Zadanie

Napisz funkcję, która sprawdza czy podany string jest palindromem. Palindrom to tekst brzmiący tak samo czytany od lewej do prawej i od prawej do lewej. Ignoruj spacje i wielkość liter.

Przykłady: "kayak", "Ala", "kobyła ma mały bok", "A man a plan a canal Panama"

Czego szuka rekruter

Rekruter sprawdza czy kandydat:

• Normalizuje wejście przed porównaniem (małe litery, usunięcie spacji/interpunkcji)
• Zna metodę dwóch wskaźników jako O(1) pamięci alternatywę dla odwracania
• Obsługuje null, pusty string, jeden znak
• Myśli o tym co “ignorować” — tylko spacje? Interpunkcję? Cyfry?

Edge cases

✅ Rozwiązanie 1 — odwracanie po normalizacji

static bool IsPalindrome(string? text)
{
    if (string.IsNullOrWhiteSpace(text))
        return false;

    // Normalizacja: tylko litery i cyfry, małe litery
    string normalized = new string(
        text.Where(c => char.IsLetterOrDigit(c))
            .Select(char.ToLowerInvariant)
            .ToArray());

    return normalized == new string(normalized.Reverse().ToArray());
}

Czytelne, ale tworzy dwa dodatkowe stringi — O(n) pamięci. To dokładnie ten sam wzorzec odwracania stringa, który szczegółowo omawiam w osobnym zadaniu rekrutacyjnym o odwracaniu stringa — łącznie z pułapkami Unicode, które dotyczą też palindromów zawierających emoji czy znaki spoza BMP.

✅ Rozwiązanie 2 — dwa wskaźniki (O(1) pamięci)

static bool IsPalindromeTwoPointers(string? text)
{
    if (string.IsNullOrWhiteSpace(text))
        return false;

    int left = 0, right = text.Length - 1;

    while (left < right)
    {
        // Pomiń znaki niebędące literami/cyframi
        while (left < right && !char.IsLetterOrDigit(text[left]))
            left++;
        while (left < right && !char.IsLetterOrDigit(text[right]))
            right--;

        if (char.ToLowerInvariant(text[left]) != char.ToLowerInvariant(text[right]))
            return false;

        left++;
        right--;
    }

    return true;
}

Nie alokuje dodatkowej pamięci — sprawdza in-place porównując znaki od obu końców jednocześnie.

Złożoność — które rozwiązanie wybrać

Oba rozwiązania mają tę samą złożoność czasową O(n), ale różną pamięciową — to właśnie ta różnica jest tym, o co pyta rekruter, nie sama poprawność wyniku.

Normalizacja dla tekstu polskiego

char.ToLowerInvariant('Ą') zwróci 'ą' — ale char.IsLetter('ą') zwróci true, więc polskie znaki są obsłużone. Ważne żeby używać ToLowerInvariant (nie ToLower) dla deterministycznych wyników niezależnie od locale.

// "kobyła ma mały bok" po normalizacji → "kobylamamalybok"
// Reversed: "kobylamamalybok" → palindrom!

Testy jednostkowe

[Theory]
[InlineData("kayak", true)]
[InlineData("level", true)]
[InlineData("radar", true)]
[InlineData("Ala", true)]
[InlineData("kobyła ma mały bok", true)]
[InlineData("A man a plan a canal Panama", true)]
[InlineData("hello", false)]
[InlineData("race a car", false)]
public void IsPalindrome_ReturnsCorrectResult(string input, bool expected)
{
    Assert.Equal(expected, IsPalindrome(input));
}

[Theory]
[InlineData(null, false)]
[InlineData("", false)]
[InlineData("   ", false)]
public void IsPalindrome_EmptyOrNull_ReturnsFalse(string? input, bool expected)
{
    Assert.Equal(expected, IsPalindrome(input));
}

[Fact]
public void IsPalindrome_SingleChar_ReturnsTrue()
{
    Assert.True(IsPalindrome("a"));
}

Co powiedzieć na rozmowie

“Przed porównaniem normalizuję wejście — usuwam spacje, interpunkcję i konwertuję na lowercase. Dla wydajności wersja z dwoma wskaźnikami jest lepsza — nie tworzy dodatkowych stringów, sprawdza in-place od obu końców jednocześnie. ToLowerInvariant zamiast ToLower zapewnia deterministyczne wyniki niezależnie od locale systemu.”

FAQ

Czy pusty string powinien być traktowany jako palindrom?
Matematycznie tak — pusty ciąg czyta się tak samo w obie strony. W kodzie powyżej zwracamy jednak false dla pustego/białego wejścia, bo w praktyce rekrutacyjnej częściej oczekuje się jawnej walidacji “brak sensownych danych” niż formalnej poprawności matematycznej — warto tę decyzję świadomie zakomunikować na rozmowie, zamiast zgadywać.

Czy warto pisać wersję rekurencyjną?
Można, ale ma te same wady co rekurencyjne odwracanie stringa (patrz artykuł o odwracaniu) — O(n) klatek na stosie bez korzyści względem wersji iteracyjnej z dwoma wskaźnikami. Rzadko warta pokazania, chyba że rekruter jawnie o nią poprosi.

Powiązane: zobacz manipulację stringów w C# i pokrewne zadanie Podciągi stringa.