MorseCodeCorrector

SRM 830 · 2022-05-27 · by misof

SRM 830 · 2022-05-27 · by misof · Dynamic Programming

Show categories

Class Name: MorseCodeCorrector

Return Type: String

Method Name: fix

Arg Types: (string)

Problem Statement

In Morse code, each character is represented by a finite sequence of dots ('.') and dashes ('-'). Below are the codes of all letters:

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 --..

An operator was listening to a Morse code transmission. The operator wrote down the received message, using dots, dashes, and pipes ('|') as separators. The separator is used exactly once between consecutive characters within a word and exactly twice between consecutive words.

For example, the two-word phrase "TOP CODER" produces the following message: "-|---|.--.||-.-.|---|-..|.|.-."

You are given the String message: the sequence of characters written down by the operator. It is possible that the operator made some mistakes and the sequence is not a valid transmission. Fix the mistakes and produce a valid message. You may only change characters to other characters, you are not allowed to completely erase them or to insert new ones. Find and return any one solution that requires the smallest total number of changes.

--------------------------

For reference, valid messages are precisely those defined by the grammar below:


[valid_message] ::= [valid_word]   or   [valid_word] + "||" + [valid_message]
[valid_word]    ::= [valid_letter]   or   [valid_letter] + "|" + [valid_word]
[valid_letter]  ::= [code_of_A]   or   [code_of_B]   or   ...   or   [code_of_Z]

Notes

For each positive x there is at least one valid message of length x, which makes the answer well-defined.

Constraints

message will contain between 1 and 2,500 characters, inclusive.
Each character of message will be '.', '-', or '|'.

Examples

"-..."
Returns: "-..."

This is the code of the letter B. A valid letter is a valid word, and a valid word is a valid message, so there's nothing to correct. We must return "-...".

"---."
Returns: "-.-."

This is not the valid code of any letter. There are many ways to fix it by making exactly one change, so you have to return one of those messages. These are all distinct valid answers for this example: ".--." ("P"), "-.-." ("C"), "--.." (Z), "-|-." ("TN"), and "--|." ("ME").

"-.-.-"
Returns: "-.|.-"

No letter has a 5-symbol code, so we must have at least one separator. There are three ways to produce a valid message by changing one of the characters to a separator.

".||-"
Returns: ".||-"

This is a valid message that consists of two separate one-letter words: "E T".

"-|---|.--.||-.-.|---|-..|.|.-."
Returns: "-|---|.--.||-.-.|---|-..|.|.-."

Another valid message: "TOP CODER".

Submissions are judged against all 153 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MorseCodeCorrector with a public method string fix(string message) · 153 test cases · 2 s / 256 MB per case