algoadvance

Leetcode Problem 2325, “Decode the Message,” requires you to decode a message using a substitution cipher. A substitution cipher replaces each letter in the alphabet with another letter, mapping each letter to a different one.

Given two strings, key and message, where key defines the substitution rule and message is the encoded message, you must decode the message.

• key is a string containing lowercase English letters and spaces, and each letter appears only once.
• The encoded message message only contains lowercase English letters and spaces.

You need to decode the message and return it.

Clarifying Questions

1. Are there any constraints on the length of key or message?
2. Are spaces in the message and key to be ignored or mapped directly?

For the sake of clarity, let’s assume:

• key is of length exactly 26 (one for each letter of the alphabet).
• message can be of any length but will contain only lowercase letters and spaces.

Strategy

1. Create a Mapping Dictionary: Use the key to create a mapping from each letter to another letter in the alphabet.
2. Decode the Message: Iterate through the message, replacing each letter according to the created mapping.
3. Handle Spaces: Ensure spaces remain unchanged in the decoded message.

Steps

1. Create a dictionary using the key to map each character to an actual letter (‘a’ to ‘z’).
2. Traverse through the message and substitute each letter using this dictionary. For spaces, keep them as is.
3. Construct the decoded message from the substitutions.

Code

def decodeMessage(key: str, message: str) -> str:
    # Remove duplicates from key while maintaining order
    seen = set()
    key = ''.join([x for x in key if not (x in seen or seen.add(x))])
    
    # Create the mapping dictionary
    substitution = dict()
    for i, char in enumerate(key):
        if char != ' ':
            substitution[char] = chr(ord('a') + i)
    
    # Decode the message
    decoded_message = []
    for char in message:
        if char == ' ':
            decoded_message.append(' ')
        else:
            decoded_message.append(substitution[char])
    
    return ''.join(decoded_message)

# Example usage:
key = "the quick brown fox jumps over a lazy dog"
message = "vkbs bs t suepuv"
print(decodeMessage(key, message))  # Output: "this is a secret"

Time Complexity

• O(N) where N is the length of the message. Creating the substitution dictionary takes constant time (since we process a fixed 26 characters from key), and decoding involves a linear scan of the message.

By constructing the mapping once and reusing it to decode the message, this solution ensures efficiency.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?