Katkat
Back

Decode Ambiguous Morse Messages

SealthSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates string parsing, pattern matching, and combinatorial decoding skills using a Morse-to-letter mapping, covering both deterministic separator handling and enumeration of ambiguous letter partitions.

You are given a mapping from Morse patterns to lowercase English letters.

Implement two related functions:

  1. Deterministic decoding with character and word separators
  • Input: a Morse-encoded string, a char_sep that separates letters inside a word, and a word_sep that separates words.
  • Output: the decoded sentence.
  • Example: if char_sep separates letters and word_sep separates words, decode the full message by splitting on words first and then on characters.
  1. Enumerate all valid decodings when character separators are missing
  • Input: a Morse-encoded string that contains only a word_sep between encoded words, but no separator between letters inside each word.
  • Because each encoded word may be partitioned into letters in multiple valid ways, return all possible decoded sentences as a list or set.
  • For each encoded word, generate every valid letter sequence whose Morse concatenation matches that word exactly, then combine the per-word results into full-sentence outputs.

Assume the Morse-to-letter dictionary is provided as part of the problem.