How do you solve Decode the Message on LeetCode?

Decode the Message (LeetCode #2325) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The mapping is based on the first appearance of characters in the key.

What algorithm or data structure is used to solve Decode the Message?

Decode the Message uses the following concepts: Hash Table, String. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Decode the Message?

Clearly explain your thought process while coding. Test your solution with edge cases, such as keys with repeated characters. Be mindful of the space complexity, especially when dealing with large inputs.

What are common mistakes when solving Decode the Message?

Not checking if a character is already in the mapping, leading to incorrect substitutions. Forgetting to handle spaces correctly.

Decode the Message — LeetCode #2325 (Easy)

Tags: Hash Table, String

Related patterns: Hash Map, Array

Brute Force approach

Time complexity: O(n²). Space complexity: O(1).

The brute force approach involves manually mapping each character in the key to the corresponding character in the alphabet. This is straightforward but inefficient, as it requires checking each character multiple times.

The time complexity is O(n²) because for each character in the message, we may need to check against all characters in the key to find the mapping, leading to multiple iterations.

Step 1: Create an empty mapping for characters from the key to the alphabet.
Step 2: Iterate through each character in the key. For each character, if it hasn't been mapped yet, assign it the next available letter from the alphabet.
Step 3: For each character in the message, replace it with the corresponding character from the mapping, leaving spaces unchanged.

1. Key: 'the quick brown fox jumps over the lazy dog', Message: 'vkbs bs t suepuv' 2. Mapping: { 't': 'a', 'h': 'b', 'e': 'c', 'q': 'd', 'u': 'e', 'i': 'f', 'k': 'g', 'b': 'h', 'r': 'i', 'o': 'j', 'w': 'k', 'n': 'l', 'f': 'm', 'x': 'n', 'j': 'o', 'm': 'p', 'p': 'q', 's': 'r', 'v': 's', 'l': 't', 'a': 'u', 'z': 'v', 'y': 'w', 'g': 'x', 'd': 'y' } 3. Decode 'v' -> 's', 'k' -> 'g', 'b' -> 'h', 's' -> 'r', ' ' -> ' ', 'b' -> 'h', 's' -> 'r', ' ' -> ' ', 't' -> 'a', ' ' -> ' ', 's' -> 'r', 'u' -> 'e', 'e' -> 'c', 'p' -> 'q', 'u' -> 'e', 'v' -> 's'. Final output: 'this is a secret'.

Optimal Solution approach

Time complexity: O(n). Space complexity: O(1).

The optimal solution efficiently constructs the mapping in a single pass through the key and then decodes the message in another pass, making it much faster than the brute force approach.

The time complexity is O(n) because we only make a single pass through the key and another pass through the message, making it efficient. The space complexity is O(1) since the mapping size is constant (26 letters).

Step 1: Initialize an empty mapping and a variable to track the next available letter in the alphabet.
Step 2: Iterate through the key, adding each unique character to the mapping until all 26 letters are mapped.
Step 3: Create the decoded message by replacing each character in the message using the mapping.

Key Insights

The mapping is based on the first appearance of characters in the key.
Spaces are preserved in the message and do not affect the mapping.

Common Mistakes

Not checking if a character is already in the mapping, leading to incorrect substitutions.
Forgetting to handle spaces correctly.

Interview Tips

Clearly explain your thought process while coding.
Test your solution with edge cases, such as keys with repeated characters.
Be mindful of the space complexity, especially when dealing with large inputs.

#2325

Decode the Message

Easy

Hash Table↗String↗Hash Map↗Array↗

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution efficiently constructs the mapping in a single pass through the key and then decodes the message in another pass, making it much faster than the brute force approach.

⚙️

Algorithm

3 steps

1Step 1: Initialize an empty mapping and a variable to track the next available letter in the alphabet.
2Step 2: Iterate through the key, adding each unique character to the mapping until all 26 letters are mapped.
3Step 3: Create the decoded message by replacing each character in the message using the mapping.

solution.py14 lines

1# Full working Python code
2key = 'the quick brown fox jumps over the lazy dog'
3message = 'vkbs bs t suepuv'
4
5mapping = {}
6alpha = 'abcdefghijklmnopqrstuvwxyz'
7next_char = 0
8for char in key:
9    if char != ' ' and char not in mapping:
10        mapping[char] = alpha[next_char]
11        next_char += 1
12
13decoded_message = ''.join(mapping.get(char, char) for char in message)
14print(decoded_message)

ℹ

Complexity note: The time complexity is O(n) because we only make a single pass through the key and another pass through the message, making it efficient. The space complexity is O(1) since the mapping size is constant (26 letters).

1The mapping is based on the first appearance of characters in the key.
2Spaces are preserved in the message and do not affect the mapping.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.