Grade 10 · Character stringsCitește în română

Checking a palindrome string

Original: Verificarea unui șir palindrom

O(n)C++1747 lines2 examples

The idea

First we keep only the letters, turned into lowercase (so 'Ele fac cafele' becomes 'elefaccafele'). Then we use two indices: st starts at the beginning, dr at the end; while st < dr we compare t[st] with t[dr] and move the indices closer. At the first different pair the string is not a palindrome.

Original description (Romanian)

Întâi păstrăm doar literele, transformate în minuscule (așa „Ele fac cafele” devine „elefaccafele”). Apoi folosim doi indici: st pornește de la început, dr de la sfârșit; cât timp st < dr comparăm t[st] cu t[dr] și apropiem indicii. La prima pereche diferită șirul nu este palindrom.

Complexity
O(L)
Grade
Grade 10 (Clasa a X-a)

Examples

Example 1

Input

Ele fac cafele

Expected output

DA
Example 2

Input

Ana are mere

Expected output

NU

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

verificare-palindrom.cpp
/*
 * Titlu: Verificarea unui șir palindrom
 * Clasa: 10
 * Capitol: Șiruri de caractere
 * Descriere: Întâi păstrăm doar literele, transformate în minuscule (așa
 *            „Ele fac cafele” devine „elefaccafele”). Apoi folosim doi indici: st
 *            pornește de la început, dr de la sfârșit; cât timp st < dr comparăm
 *            t[st] cu t[dr] și apropiem indicii. La prima pereche diferită șirul
 *            nu este palindrom.
 * Complexitate: O(L)
 *
 * Exemplu
 * Intrare: Ele fac cafele
 * Ieșire: DA
 *
 * Exemplu
 * Intrare: Ana are mere
 * Ieșire: NU
 */
#include <iostream>
#include <cctype>
using namespace std;

int main()
{
    char s[256], t[256];
    cin.getline(s, 256);

    int k = 0;
    for (int i = 0; s[i] != '\0'; i++)
        if (isalpha(s[i]))
            t[k++] = tolower(s[i]);
    t[k] = '\0';

    bool palindrom = true;
    int st = 0, dr = k - 1;
    while (st < dr && palindrom)
    {
        if (t[st] != t[dr])
            palindrom = false;
        st++;
        dr--;
    }
    cout << (palindrom ? "DA" : "NU") << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.