Palindroame — citit la fel în ambele sensuri

De ce contează?

„ele", „cojoc", „aerisirea" — citește-le invers. Sunt la fel! Un palindrom e un text care arată identic citit de la stânga la dreapta și de la dreapta la stânga. Ca o oglindă pusă fix la mijlocul cuvântului: cele două jumătăți se reflectă una pe cealaltă.

Ce este un palindrom

Un șir e palindrom dacă, citit de la coadă la cap, rămâne neschimbat. Asta înseamnă că primul caracter trebuie să fie egal cu ultimul, al doilea cu penultimul ș.a.m.d. — caracterele simetrice față de centru coincid.

Observația-cheie

Nu trebuie să compari fiecare caracter cu fiecare. E de ajuns să verifici perechile simetrice: s[0] cu s[n-1], s[1] cu s[n-2], ... până te întâlnești la mijloc.

Algoritmul cu doi indici

Pornim cu st = 0 (stânga) și dr = n-1 (dreapta) și înaintăm unul spre celălalt. Pentru "cojoc":

s	c	o	j	o	c
index	0	1	2	3	4
	st				dr

Pas 1: s[0]='c' == s[4]='c' → potrivire, avansăm st→1, dr→3.

s	c	o	j	o	c
index	0	1	2	3	4
		st		dr

Pas 2: s[1]='o' == s[3]='o' → potrivire. st=2, dr=2 se întâlnesc → palindrom.

st=0 dr=4 : 'c' == 'c'  ok -> st=1 dr=3
st=1 dr=3 : 'o' == 'o'  ok -> st=2 dr=2
st >= dr  : ne-am intalnit -> PALINDROM

Implementare C++

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

bool estePalindrom(const string& s) {
    int st = 0, dr = s.size() - 1;
    while (st < dr) {
        if (s[st] != s[dr]) {
            return false;        // o nepotrivire => nu e palindrom
        }
        st++;
        dr--;
    }
    return true;
}

int main() {
    cout << estePalindrom("cojoc") << endl;  // 1
    cout << estePalindrom("carte") << endl;  // 0
    return 0;
}

Complexitate

Caz	Timp	Spațiu
Cel mai bun (nepotrivire la primul pas)	O(1)	O(1)
Cel mai rău (chiar e palindrom)	O(n/2) = O(n)	O(1)

Metoda nu folosește memorie suplimentară și se oprește imediat ce găsește o diferență.

Greșeli frecvente

Greșeli des întâlnite:

dr = s.size() în loc de s.size() - 1. size() e poziția de după ultimul caracter; pornind de acolo, compari cu un caracter inexistent.
s.size() - 1 pe șir gol. size() e unsigned: pe șir gol devine un număr uriaș. Tratează separat șirul vid (de obicei e considerat palindrom).
Construiești inversul degeaba. A copia tot șirul inversat și a-l compara merge, dar costă O(n) memorie în plus și nu se oprește devreme. Doi indici e mai bun.
Uiți să tratezi diferit literele mari/mici sau spațiile când problema cere asta (de ex. „A man a plan..."). Citește cu atenție ce caractere contează.

Recapitulare

Un palindrom se citește la fel în ambele sensuri: caracterele simetrice coincid.
Verifici cu doi indici, din capete spre centru, în O(n) timp și O(1) memorie.
Oprește-te la prima nepotrivire și tratează cu grijă șirul vid (size() e unsigned).