Разбор задачи «Декодирование азбуки Морзе»

1. Идея

Нужно прочитать строку, состоящую из кодов Морзе, и заменить каждый код на соответствующую букву или цифру.

Формат удобный:

• код одного символа — это последовательность из . и -;
• соседние символы разделены пробелом;
• между словами стоит отдельный токен /.

Значит, достаточно:

1. заранее сохранить таблицу соответствий код Морзе -> символ;
2. разбить входную строку на части по пробелам;
3. пройти по всем частям:
   • если встретили /, добавить пробел в ответ;
   • иначе декодировать по таблице.

2. Наблюдения

Наблюдение 1. Удобно хранить именно обратную таблицу

Обычно азбуку Морзе знают как A -> .-, B -> -... и так далее. Но в задаче нам нужно делать обратное преобразование: по строке .- получать A.

Поэтому удобно сразу завести словарь:

• в C++: unordered_map<string, char>
• в Python: dict

где ключ — код Морзе, а значение — символ.

Наблюдение 2. Символ / уже отделён пробелами

По условию между словами стоит ровно ' / ', то есть / можно считать обычным отдельным токеном.

Например, строка

... --- ... / ..--- ----- ..--- ....-

после разбиения по пробелам превратится в последовательность:

• ...
• ---
• ...
• /
• ..---
• -----
• ..---
• ....-

Это очень упрощает решение: не нужно отдельно искать границы слов.

Наблюдение 3. Все коды корректны

По условию вход всегда правильный. Значит, можно не проверять, существует ли код в таблице: он точно существует.

3. Алгоритм

1. Создать таблицу соответствий для всех:

   • букв A-Z,
   • цифр 0-9.

2. Считать всю строку сообщения.

3. Разбить её на токены по пробелам.

4. Для каждого токена:

   • если токен равен /, добавить в ответ пробел;
   • иначе найти этот код в таблице и добавить соответствующую букву или цифру.

5. Вывести полученную строку.

4. Почему это работает

Рассмотрим любой токен входной строки после разбиения по пробелам.

Случай 1. Токен равен /

По условию / отделяет одно слово от другого. Значит, в восстановленном тексте на этом месте должен стоять пробел. Именно это алгоритм и делает.

Случай 2. Токен состоит из . и -

По условию это корректный код одной заглавной буквы или одной цифры международной азбуки Морзе. Таблица содержит точное соответствие для каждого такого кода, поэтому алгоритм добавляет ровно тот символ, который был закодирован.

Так как алгоритм обрабатывает токены слева направо и для каждого токена выполняет правильное действие, итоговая строка полностью совпадает с исходным сообщением.

5. Сложность

Пусть n — длина входной строки.

• Разбиение строки на токены занимает O(n).
• Обход токенов тоже занимает O(n).
• Поиск в словаре в среднем работает за O(1) на токен.

Итоговая сложность: O(n).

Дополнительная память:

• таблица Морзе постоянного размера;
• список токенов и ответ — O(n).

6. Код на C++17

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

int main() {
    unordered_map<string, char> morse;
    morse[".-"] = 'A';
    morse["-..."] = 'B';
    morse["-.-."] = 'C';
    morse["-.."] = 'D';
    morse["."] = 'E';
    morse["..-."] = 'F';
    morse["--."] = 'G';
    morse["...."] = 'H';
    morse[".."] = 'I';
    morse[".---"] = 'J';
    morse["-.-"] = 'K';
    morse[".-.."] = 'L';
    morse["--"] = 'M';
    morse["-."] = 'N';
    morse["---"] = 'O';
    morse[".--."] = 'P';
    morse["--.-"] = 'Q';
    morse[".-."] = 'R';
    morse["..."] = 'S';
    morse["-"] = 'T';
    morse["..-"] = 'U';
    morse["...-"] = 'V';
    morse[".--"] = 'W';
    morse["-..-"] = 'X';
    morse["-.--"] = 'Y';
    morse["--.."] = 'Z';

    morse["-----"] = '0';
    morse[".----"] = '1';
    morse["..---"] = '2';
    morse["...--"] = '3';
    morse["....-"] = '4';
    morse["....."] = '5';
    morse["-...."] = '6';
    morse["--..."] = '7';
    morse["---.."] = '8';
    morse["----."] = '9';

    string line;
    getline(cin, line);

    stringstream ss(line);
    string token;
    string result;

    while (ss >> token) {
        if (token == "/") {
            result += ' ';
        } else {
            result += morse[token];
        }
    }

    cout << result << '\n';
    return 0;
}

7. Код на Python 3

morse = {
    ".-": "A",
    "-...": "B",
    "-.-.": "C",
    "-..": "D",
    ".": "E",
    "..-.": "F",
    "--.": "G",
    "....": "H",
    "..": "I",
    ".---": "J",
    "-.-": "K",
    ".-..": "L",
    "--": "M",
    "-.": "N",
    "---": "O",
    ".--.": "P",
    "--.-": "Q",
    ".-.": "R",
    "...": "S",
    "-": "T",
    "..-": "U",
    "...-": "V",
    ".--": "W",
    "-..-": "X",
    "-.--": "Y",
    "--..": "Z",
    "-----": "0",
    ".----": "1",
    "..---": "2",
    "...--": "3",
    "....-": "4",
    ".....": "5",
    "-....": "6",
    "--...": "7",
    "---..": "8",
    "----.": "9",
}

tokens = input().split()
result = []

for token in tokens:
    if token == "/":
        result.append(" ")
    else:
        result.append(morse[token])

print("".join(result))