De ce contează?
Cuvântul „cojoc” se citește la fel de la stânga la dreapta și de la dreapta la stânga. La fel „rotor”, sau numele „Ana”. Astfel de cuvinte, care arată identic și citite invers, se numesc palindroame. Cum verifici, fără să întorci tot cuvântul pe dos, dacă un șir e palindrom?
Intuiția
Un palindrom e simetric: prima literă trebuie să fie egală cu ultima, a doua cu penultima, și tot așa spre mijloc. Așază două degete pe șir — unul pe prima literă, unul pe ultima — și compară perechea. Dacă se potrivesc, mută ambele degete cu un pas spre centru și compară din nou. Dacă oricând cele două litere diferă, cuvântul nu e palindrom. Dacă degetele se întâlnesc la mijloc fără să fi găsit vreo nepotrivire, e palindrom.
Vezi cum funcționează
Urmărește cei doi indici cum pornesc de la capete și se apropie unul de altul, comparând câte o pereche de litere la fiecare pas.
Folosește ← și → ca să pășești pereche cu pereche, sau Redă pentru animație. Observă cum cei doi indici se apropie de centru și că verificarea se oprește în clipa în care o pereche nu se potrivește.
Prima idee: construiesc inversul șirului (îl scriu de la coadă spre cap) și verific dacă șirul inversat e identic cu cel original. Dacă da, e palindrom.
Funcționează, dar e risipă. Ca să ții inversul ai nevoie de un al doilea șir — memorie în plus O(n) — și faci două parcurgeri: una ca să-l construiești, alta ca să-l compari. În plus, chiar dacă prima și ultima literă diferă deja, construiești tot inversul înainte să afli răspunsul.
Nu am nevoie de o copie inversată ca să compar simetric. Pun doi indici: st la
început (poziția 0) și dr la sfârșit (poziția n-1). Aceștia sunt fix perechea
„prima cu ultima". Dacă litera de la st diferă de cea de la dr, am terminat:
nu e palindrom.
Cât timp st este mai mic decât dr, compar s[st] cu s[dr]. Dacă diferă,
returnez „nu e palindrom". Dacă sunt egale, avansez: st crește, dr scade.
Când indicii se întâlnesc, e palindrom. O singură parcurgere, fără șir auxiliar:
O(n) timp, O(1) spațiu.
Algoritmul pas cu pas
Verificăm șirul "rotor", cu literele pe pozițiile 0–4. Punem st = 0 și
dr = 4.
Pasul 1. st = 0, dr = 4. Comparăm s[0] = 'r' cu s[4] = 'r': egale,
deci avansăm st la 1 și coborâm dr la 3.
r | o | t | o | r |
0 | 1 | 2 | 3 | 4 |
st | dr |
Pasul 2. st = 1, dr = 3. Comparăm s[1] = 'o' cu s[3] = 'o': egale,
deci st urcă la 2 și dr scade la 2.
r | o | t | o | r |
0 | 1 | 2 | 3 | 4 |
st | dr |
Pasul 3. Acum st = 2 și dr = 2: indicii s-au întâlnit, deci st nu mai
este mai mic decât dr. Bucla se oprește — toate perechile s-au potrivit, deci
"rotor" este palindrom.
r | o | t | o | r |
0 | 1 | 2 | 3 | 4 |
st-dr |
Acum șirul "carte", tot pe pozițiile 0–4, cu st = 0 și dr = 4.
Pasul 1. Comparăm s[0] = 'c' cu s[4] = 'e': diferă! Ne oprim imediat —
"carte" nu este palindrom, și o știm din prima comparație.
c | a | r | t | e |
0 | 1 | 2 | 3 | 4 |
st | dr |
Indicii se apropie cu câte un pas fiecare, deci faci cel mult n/2 comparații.
Și mai bine: la un șir care nu e palindrom te oprești la prima nepotrivire, fără
să mai parcurgi restul.
Implementare C++
#include <iostream>
#include <string>
using namespace std;
bool palindrom(string s) {
int st = 0;
int dr = s.size() - 1;
while (st < dr) {
// compar perechea simetrica: prima cu ultima, etc.
if (s[st] != s[dr]) {
return false; // o pereche difera -> nu e palindrom
}
st++; // avansez spre centru din stanga
dr--; // avansez spre centru din dreapta
}
return true; // toate perechile s-au potrivit
}
int main() {
cout << palindrom("rotor") << endl; // 1 (DA: r=r, o=o, t centru)
cout << palindrom("carte") << endl; // 0 (NU: c difera de e)
return 0;
}Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Cel mai bun (diferă prima pereche) | O(1) | O(1) |
| Mediu / cel mai rău (palindrom) | O(n) | O(1) |
Folosești doar doi indici și nicio copie a șirului, deci spațiul suplimentar e constant, O(1). Comparând câte o pereche și apropiind indicii, parcurgi cel mult jumătate din șir — O(n) în cel mai rău caz.
Greșeala clasică: compari toate cele n poziții (de la st = 0 până la
dr = n-1) în loc să te oprești la mijloc. Asta dublează munca — fiecare pereche
ajunge comparată de două ori (o dată ca (st, dr), o dată ca (dr, st)), iar pe
șirurile lungi e timp pierdut degeaba. Condiția corectă este st < dr: când
indicii se ating ești pe litera centrală și nu mai ai ce verifica.
A doua capcană: dacă enunțul cere să ignori spațiile sau diferența dintre litere mari și mici („Ana” față de „ana”, sau o propoziție cu spații), trebuie să le tratezi explicit — de exemplu sări peste spații sau transformi totul în litere mici înainte de comparație. Altfel un palindrom „cu spații” va fi raportat greșit.