Palindroame — citit la fel în ambele sensuri

De ce contează?

Cuvinte ca „cojoc” sau „rotor” se citesc identic și de la stânga la dreapta, și invers. Sunt simetrice ca o oglindă pusă la mijloc. A verifica un palindrom înseamnă a verifica exact această simetrie.

Ce este un palindrom?

Un palindrom este un șir care se citește la fel în ambele sensuri: "cojoc", "rotor", "aba". Formal, caracterul de pe poziția i trebuie să fie egal cu cel de pe poziția simetrică n - 1 - i.

Ideea cu doi pointeri

Nu ai nevoie să inversezi nimic. Pui un deget la început (st) și unul la final (dr) și îi apropii, comparând perechile:

s	r	o	t	o	r
index	0	1	2	3	4
	st				dr

Pas 1: comparăm s[st]=r cu s[dr]=r → egale, apropiem capetele.

s	r	o	t	o	r
index	0	1	2	3	4
		st		dr

Pas 2: o = o; rămâne mijlocul (index 2), care nu are pereche → palindrom.

La prima nepotrivire știi sigur că nu e palindrom și te oprești. Dacă pointerii se întâlnesc fără nepotriviri, este palindrom.

Algoritmul pas cu pas

Fie s = "rotor" (n = 5):

st = 0, dr = 4: r == r → avansăm → st = 1, dr = 3
st = 1, dr = 3: o == o → avansăm → st = 2, dr = 2
st >= dr → ne-am întâlnit la mijloc → palindrom

Implementare C++

#include <iostream>
#include <string>
using namespace std;

bool estePalindrom(string s) {
    int st = 0, dr = s.size() - 1;
    while (st < dr) {
        if (s[st] != s[dr]) return false;  // capete diferite -> nu
        st++;
        dr--;
    }
    return true;                            // toate perechile au fost egale
}

int main() {
    cout << estePalindrom("rotor") << "\n";  // 1
    cout << estePalindrom("carte") << "\n";  // 0
    cout << estePalindrom("a")     << "\n";  // 1 (un caracter e palindrom)
    return 0;
}

Observația-cheie

Bucla while (st < dr) se oprește singură la mijloc: pentru lungime impară, caracterul din centru nu are pereche și nu trebuie verificat. Eleganța metodei: zero memorie suplimentară.

Varianta cu inversare (corectă, dar mai scumpă)

Un palindrom este egal cu propriul invers. Merge, dar costă O(n) memorie:

#include <algorithm>
bool palindromInvers(string s) {
    string t = s;
    reverse(t.begin(), t.end());   // inverseaza copia
    return s == t;                 // egale <=> palindrom
}

Complexitate

Metodă	Timp	Spațiu
Doi pointeri	O(n)	O(1)
Comparație cu inversul	O(n)	O(n)

Greșeli frecvente

Greșeli frecvente de concurs:

dr = s.size() - 1 pe șir gol: size() e fără semn; pe șir gol dr devine uriaș. Tratează separat s.empty() sau folosește (int)s.size() - 1.
while (st <= dr): la st == dr compari un caracter cu el însuși — inofensiv, dar inutil; st < dr e curat.
Spații și majuscule: „A man a plan” e palindrom doar dacă ignori spațiile și cazul. Citește cerința: filtrezi întâi sau nu.
Confuzia simetriei: poziția simetrică a lui i este n - 1 - i, nu n - i.

Recapitulare

Un palindrom satisface s[i] == s[n-1-i] pentru toate pozițiile.
Metoda cu doi pointeri apropie capetele și se oprește la prima nepotrivire — O(n) timp, O(1) memorie.
Comparația cu inversul e corectă, dar folosește O(n) memorie în plus.