Parcurgerea unui string caracter cu caracter

Intuiția

Un string este o secvență de caractere numerotate de la 0 la s.length() - 1 — practic un vector de litere. Multe întrebări despre un text se reduc la „uită-te la fiecare caracter o dată”: câte vocale are? câte cifre? cum arată scris cu majuscule?

Cheia este că nu ai nevoie de mai multe treceri. La fiecare caracter poți decide pe loc ce-i actualizezi, iar la final ai toate răspunsurile. O singură plimbare prin șir, cost proporțional cu lungimea lui.

Vezi cum funcționează

Urmărește cum degetul (indexul i) avansează caracter cu caracter prin șir, iar contoarele se actualizează la fiecare pas:

Algoritmul pas cu pas

Luăm șirul s = "algoritmica" și numărăm vocalele într-o singură trecere. Pornim cu vocale = 0 și mutăm indexul i de la 0 spre coadă. La fiecare caracter verificăm dacă e una dintre a, e, i, o, u:

Urmărim contorul pas cu pas, caracter cu caracter:

• i = 0: 'a' e vocală → vocale = 1
• i = 1: 'l' consoană → rămâne 1
• i = 2: 'g' consoană → rămâne 1
• i = 3: 'o' e vocală → vocale = 2
• i = 5: 'i' e vocală → vocale = 3
• i = 8: 'i' e vocală → vocale = 4
• i = 10: 'a' e vocală → vocale = 5

Implementare C++

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

int main() {
    string s = "algoritmica";

    int vocale = 0, consoane = 0, cifre = 0;
    // o singura trecere prin sir, toate contoarele deodata
    for (int i = 0; i < (int)s.length(); i++) {
        char c = s[i];
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
            vocale++;
        } else if (c >= 'a' && c <= 'z') {
            consoane++;
        } else if (c >= '0' && c <= '9') {
            cifre++;
        }
    }

    cout << vocale << "\n";     // 5 vocale
    cout << consoane << "\n";   // 6 consoane
    cout << cifre << "\n";      // 0 cifre
    return 0;
}

Aceeași parcurgere se poate scrie și cu range-based for, când ai nevoie doar de valoarea caracterului, nu de poziția lui:

int vocale = 0;
for (char c : s) {             // c ia pe rand fiecare caracter
    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
        vocale++;
    }
}
// vocale == 5 pentru "algoritmica"

Complexitate

Parcurgem șirul o singură dată (n = lungimea lui), iar pe lângă șir folosim doar câteva variabile contor, indiferent cât de lung e textul. Adăugarea de noi întrebări (consoane, cifre) nu schimbă O(n) — rămâne o singură trecere.