#2325

Easy

LeetCode Problem Workspace

Decode the Message

Decode the Message is an easy problem involving hash table mapping for string decoding based on a cipher key.

Problem Statement

You are given two strings: a cipher key and a message. The key contains every letter of the English alphabet at least once, and spaces. You must decode the message using the key, where each letter from the key corresponds to a unique letter in the alphabet based on its first occurrence in the key string. The spaces in the message should remain unchanged.

Your task is to return the decoded message by using the mapping between the cipher key and the English alphabet. For example, using a key like "the quick brown fox jumps over the lazy dog" and a message like "vkbs bs t suepuv", the decoded message would be "this is a secret".

Examples

Example 1

Input: key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv"

Output: "this is a secret"

The diagram above shows the substitution table. It is obtained by taking the first appearance of each letter in "the quick brown fox jumps over the lazy dog".

Example 2

Input: key = "eljuxhpwnyrdgtqkviszcfmabo", message = "zwx hnfx lqantp mnoeius ycgk vcnjrdb"

Output: "the five boxing wizards jump quickly"

The diagram above shows the substitution table. It is obtained by taking the first appearance of each letter in "eljuxhpwnyrdgtqkviszcfmabo".

Constraints

26 <= key.length <= 2000
key consists of lowercase English letters and ' '.
key contains every letter in the English alphabet ('a' to 'z') at least once.
1 <= message.length <= 2000
message consists of lowercase English letters and ' '.

Solution Approach

Step 1: Build the Substitution Table

Iterate through the key string and construct a hash table where each unique character in the key maps to a letter of the English alphabet based on the order of their first appearance.

Step 2: Decode the Message

Iterate through the characters of the message, and for each character, use the substitution table to find the corresponding decoded letter. If the character is a space, leave it unchanged.

Step 3: Return the Decoded Message

After decoding all characters, return the final decoded message as a string.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(N), where N is the length of the message, since we process each character once. The space complexity is O(1), as the hash table will always store 26 characters (one for each letter of the alphabet).

What Interviewers Usually Probe

The problem tests familiarity with hash table usage in string processing.
Look for clarity in the candidate’s approach to character mapping.
Watch for edge case handling like spaces in the message.

Common Pitfalls or Variants

Common pitfalls

Failing to build the substitution table correctly by not considering the first occurrence of each letter in the key.
Incorrectly handling spaces in the message.
Overcomplicating the mapping process and missing a straightforward approach.

Follow-up variants

Using a shorter key that doesn’t cover all alphabet letters.
Adding punctuation in the message or key, requiring adjustments.
Changing the alphabet to lowercase and uppercase combinations.

FAQ

What is the key pattern used in this problem?

The key pattern involves using the first occurrence of each letter from the cipher key to build a mapping to the English alphabet.

How do I handle spaces in the message?

Spaces should remain unchanged during decoding. They are not mapped to any letters.

What happens if the key is missing some letters?

The problem guarantees that the key contains every letter of the alphabet at least once, so this situation will not occur.

What is the best way to store the mapping from the key to the alphabet?

Use a hash table (or dictionary) to store the mapping, where each unique letter in the key corresponds to a letter in the English alphabet.

Can the message contain special characters?

No, the problem only considers lowercase English letters and spaces in the message.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

class Solution:
    def decodeMessage(self, key: str, message: str) -> str:
        d = {" ": " "}
        i = 0
        for c in key:
            if c not in d:
                d[c] = ascii_lowercase[i]
                i += 1
        return "".join(d[c] for c in message)

Continue Practicing

#2309 greatest english letter in upper and lower case #2306 naming a company #2301 match substring after replacement