We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Decode the Message

Difficulty: Easy

Problem Description

You are given the strings key and message, which represent a cipher key and a secret message, respectively. The steps to decode message are as follows:

  1. Use the first appearance of all 26 lowercase English letters in key as the order of the substitution table.
  2. Align the substitution table with the regular English alphabet.
  3. Each letter in message is then substituted using the table.
  4. Spaces ' ' are transformed to themselves.

Return the decoded message.

Key Insights

  • The problem requires constructing a substitution cipher based on the first appearances of letters in a given key.
  • A mapping needs to be created where each letter in the key corresponds to a letter in the standard alphabet.
  • Spaces in the message should remain unchanged while decoding.
  • The algorithm must efficiently handle the input strings and maintain the order of letters.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the key or message, as we iterate through them to build the mapping and decode the message. Space Complexity: O(1), since we only need a fixed amount of space for the mapping of the 26 letters.

Solution

To solve the problem, we follow these steps:

  1. Create a mapping from the characters in the key to the characters in the alphabet. This is done by iterating through the key and recording the first appearance of each letter.
  2. Use the mapping to transform each character in the message. If the character is a letter, it is replaced by the corresponding character from the mapping; if it's a space, it remains a space.
  3. Construct the decoded message string and return it.

The main data structure used is a dictionary for the letter mapping, and the approach is straightforward string manipulation.

Code Solutions

def decodeMessage(key: str, message: str) -> str:
    # Create the mapping dictionary
    mapping = {}
    # The English alphabet
    alphabet = 'abcdefghijklmnopqrstuvwxyz'
    
    # Fill the mapping based on the first appearance in key
    index = 0
    for char in key:
        if char != ' ' and char not in mapping:
            mapping[char] = alphabet[index]
            index += 1
            
    # Decode the message using the mapping
    decoded_message = []
    for char in message:
        if char == ' ':
            decoded_message.append(' ')
        else:
            decoded_message.append(mapping[char])
    
    return ''.join(decoded_message)
← Back to All Questions