Otkrij poruku

Data je niska cifara sastavljena od cifara 0–9. Svaka cifra predstavlja skup slova kao na klasičnoj telefonskoj tastaturi:

Potrebno je da generisati sve moguće niske koje nastaju tako što za svaku cifru iz ulaza izaberete po jedno slovo iz njenog skupa. Rezultate ispisati u strogo rastućem leksikografskom poretku (po ASCII poretku malih slova).

Opis ulaza

Sa standardnog ulaza se učitava jedna niska \(S\) (\(1 \leq |S| \leq 10\)) sastavljena samo od cifara.

Opis izlaza

Na standardni izlaz ispisati sve dobijene kombinacije, svaku u posebnom redu, u rastućem leksikografskom poretku.

Primer

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

U ovom bloku se opisuje glavno rešenje zadatka.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

static vector<string> mapping = 
{
    " ",
    "",
    "abc",
    "def",
    "ghi",
    "jkl",
    "mno",
    "pqrs",
    "tuv",
    "wxyz"
};

void gen_msgs(const string digits, const int i, string msg)
{
    if (i == digits.size()) {
        cout << msg << endl;
        return;
    }

    int num = digits[i] - '0';

    if (num == 1) {
        gen_msgs(digits, i + 1, msg);
    }

    for (char c : mapping[num]) {
        msg.push_back(c);
        gen_msgs(digits, i + 1, msg);
        msg.pop_back();
    }
}

void gen_msgs(const string digits)
{
    string msg;
    gen_msgs(digits, 0, msg);
}

int main() 
{
    string digits; cin >> digits;

    gen_msgs(digits);

    return 0;
}