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

Checking anagrams

Original: Verificarea anagramelor

O(n)C++1741 lines2 examples

The idea

Two words are anagrams if they have the same letters, the same number of times, in a different order (for example 'roma' and 'amor'). We use a frequency array with 26 positions: for every letter of the first word we increase fr[c - 'a'], for every letter of the second we decrease it. The words are anagrams if all values are 0 at the end. The words consist of lowercase letters.

Original description (Romanian)

Două cuvinte sunt anagrame dacă au aceleași litere, de același număr de ori, în altă ordine (de exemplu „roma” și „amor”). Folosim un vector de frecvență cu 26 de poziții: pentru fiecare literă din primul cuvânt creștem fr[c - 'a'], pentru fiecare literă din al doilea o scădem. Cuvintele sunt anagrame dacă la final toate valorile sunt 0. Cuvintele sunt formate din litere mici.

Complexity
O(L1 + L2)
Grade
Grade 10 (Clasa a X-a)

Examples

Example 1

Input

roma amor

Expected output

DA
Example 2

Input

carte traca

Expected output

NU

The code

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

verificarea-anagramelor.cpp
/*
 * Titlu: Verificarea anagramelor
 * Clasa: 10
 * Capitol: Șiruri de caractere
 * Descriere: Două cuvinte sunt anagrame dacă au aceleași litere, de același număr
 *            de ori, în altă ordine (de exemplu „roma” și „amor”). Folosim un
 *            vector de frecvență cu 26 de poziții: pentru fiecare literă din primul
 *            cuvânt creștem fr[c - 'a'], pentru fiecare literă din al doilea o
 *            scădem. Cuvintele sunt anagrame dacă la final toate valorile sunt 0.
 *            Cuvintele sunt formate din litere mici.
 * Complexitate: O(L1 + L2)
 *
 * Exemplu
 * Intrare: roma amor
 * Ieșire: DA
 *
 * Exemplu
 * Intrare: carte traca
 * Ieșire: NU
 */
#include <iostream>
using namespace std;

int main()
{
    char a[101], b[101];
    cin >> a >> b;
    int fr[26] = {0};
    for (int i = 0; a[i] != '\0'; i++)
        fr[a[i] - 'a']++;
    for (int i = 0; b[i] != '\0'; i++)
        fr[b[i] - 'a']--;

    bool anagrame = true;
    for (int c = 0; c < 26; c++)
        if (fr[c] != 0)
            anagrame = false;
    cout << (anagrame ? "DA" : "NU") << '\n';
    return 0;
}

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