Palindroame

Intuiția

Un palindrom e simetric față de centrul lui: primul caracter trebuie să fie egal cu ultimul, al doilea cu penultimul și așa mai departe spre mijloc. Nu trebuie să compari tot șirul cu o copie întoarsă — îți ajunge să verifici că fiecare pereche de capete care se „oglindesc” coincide. Pui un deget la început și unul la final și îi apropii unul de celălalt.

Vezi cum funcționează

Pornește animația și urmărește cei doi pointeri: unul pleacă din stânga, celălalt din dreapta, și se apropie de centru. La fiecare pas compară perechea de capete; dacă toate coincid până se întâlnesc la mijloc, șirul e palindrom.

Algoritmul pas cu pas

Fie șirul rotor, cu indici de la 0 la 4. Punem st = 0 și dr = 4.

Pasul 1. Comparăm capetele: s[0] cu s[4].

Pasul 2. Avansăm: st = 1, dr = 3. Comparăm s[1] cu s[3].

Pasul 3. Acum st = 2, dr = 2: pointerii s-au întâlnit la mijloc.

Nicio pereche n-a diferit, deci rotor este palindrom.

Pentru contrast, pe carte: prima pereche e s[0]='c' și s[4]='e'. Sunt diferite, deci te oprești imediat — carte nu este palindrom, fără să mai verifici restul.

Implementare C++

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

// returneaza true daca s se citeste la fel in ambele sensuri
bool estePalindrom(const string &s) {
    int st = 0;
    int dr = s.size() - 1;
    while (st < dr) {
        if (s[st] != s[dr]) {
            return false;    // o pereche difera -> nu e palindrom
        }
        st++;                // avansam spre centru
        dr--;
    }
    return true;             // toate perechile au coincis
}

int main() {
    string s = "rotor";
    if (estePalindrom(s)) {
        cout << s << " este palindrom";
    } else {
        cout << s << " nu este palindrom";
    }
    // rotor este palindrom
    return 0;
}

Complexitate

Verifici cel mult n/2 perechi, deci timpul e O(n). Nu construiești nicio copie, folosești doar doi indici, deci memoria suplimentară e O(1).