2325. Decode the Message
Problem Description
The given problem presents a scenario where a secret message needs to be decoded using a cipher key. The cipher key is a string that contains all 26 lowercase English letters, where the first occurrence of each letter represents its position in the cipher table. The process of decoding involves creating a substitution table based on the first appearance of each letter in the key and then mapping that to the regular English alphabet in order (a-z).
To decode the message, each letter in the message is substituted with the corresponding letter from the substitution table. It is crucial to note that spaces remain unchanged. The goal is to apply this substitution process to the entire message to retrieve the original text.
Intuition
The intuition behind the solution is to map each letter from the key to its position in the alphabet sequence. This is the basis for creating the substitution table. In the Python solution, a dictionary is used to store this mapping. The steps to arrive at the solution include:
- Initialize a dictionary that will hold the mapping (
d = {" ": " "}
) allowing spaces to be mapped to themselves as per the problem statement. - Iterate over each character in the key string and fill the dictionary with unique letters, assigning them to the corresponding order in the English alphabet (using the
ascii_lowercase[i]
). The variablei
is used to keep track of the position in the alphabet. - Use the dictionary to translate each character in the message. If the character is a space, it maps to a space; otherwise, it will be substituted according to the key-to-alphabet mapping.
- Finally, the translated characters are joined to form the decoded message which is returned as the solution.
This approach ensures that each distinct non-space character from the key is accounted for in sequential order, and then the message is decoded character by character.
Solution Approach
The solution leverages a few key concepts, primarily dictionary mapping and string iteration in Python.
-
Dictionary for Mapping: The use of a dictionary,
d
, is central to this approach. Dictionaries in Python are key-value pairs that allow for quick look-ups, insertions, and updates. Given that spaces are mapped to themselves (d = {" ": " "}
), the dictionary serves as the substitution table. -
String Iteration: The code iterates over the
key
string using afor
loop. For each characterc
found inkey
, it checks whether the character is already in the dictionary. If it is not, it means this is the first occurrence of that character and, thus, should be added to the dictionary. -
Substitution Logic: The mapping to the English alphabet is handled by
ascii_lowercase[i]
, which returns thei
-th letter from the English alphabet (contained in thestring
module from Python's standard library). The variablei
is incremented only when a new mapping is created. This ensures that each unique letter inkey
is associated with a unique letter of the alphabet in order. -
Message Decoding: Next, the code decodes
message
by iterating over every character in it. It uses the dictionaryd
to find the substitution for each character, compiles these using a list comprehension, and joins them with"".join(d[c] for c in message)
to form the final decoded message string. -
Ignoring Duplicate Letters: Since only the first occurrence of each letter is considered, subsequent ones are ignored, effectively skipping them during the dictionary mapping process.
This solution is efficient as mapping and look-up operations in dictionaries are on average O(1) in complexity. The overall decoding process depends on the lengths of the key
and message
strings, making the time complexity linear with respect to the size of the input, or O(N+M) where N is the length of key
and M is the length of message
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Suppose we are given the following cipher key:
key = "thequickbrownfoxjumpsoverlazydg"
and we want to decode this message:
message = "vkbs bs t suepr"
Here's how the solution would work step by step:
-
Dictionary for Mapping: We initialize a dictionary
d
that will hold the mapping of each character. We start with mapping spaces to themselves:d = {" ": " "}
. -
String Iteration (Creating the Substitution Table):
- We start by iterating over the
key
string. - For each character
c
in the key, we check if it's already in the dictionaryd
. - Our dictionary starts as
d = {" ": " "}
.
Iterating through the
key
:- The first character is
t
, which is not ind
, so we add it:d = {" ": " ", "t": "a"}
. - The second character is
h
, not ind
either, so we add it:d = {" ": " ", "t": "a", "h": "b"}
. - This process continues with each unique letter until the dictionary is filled with the first occurrences:
... {"x": "m", "j": "n", "u": "o", "m": "p", "p": "q", "s": "r", "o": "s", "v": "t", "e": "u", "r": "v", "l": "w", "a": "x", "z": "y", "y": "z"}
. - We ignore any subsequent occurrences of letters we've seen before.
- We start by iterating over the
-
Substitution Logic:
- We have the
ascii_lowercase
variable which is a string"abcdefghijklmnopqrstuvwxyz"
. - Each time we add a new key-value pair to the dictionary, the value is the next letter from
ascii_lowercase
that has not yet been used.
- We have the
-
Message Decoding:
- Now, we decode the
message
by looking at each character and using our dictionaryd
to find what it maps to. - Translating our example message:
"vkbs bs t suepr"
- 'v' becomes 't'
- 'k' becomes 'h'
- 'b' maps to 'i'
- 's' maps to 'r'
- and so on.
- The decoded message is formed by substituting each character in the original
message
with its mapped value fromd
.
- Now, we decode the
-
Resulting Output:
- After applying the substitution to each character, we get the final message:
"this is a super"
- The message has been successfully decoded!
- After applying the substitution to each character, we get the final message:
This example clearly demonstrates how the dictionary is created based on the first unique occurrence of each letter in the cipher key and how the message characters are then substituted according to this dictionary to reveal the original text.
Solution Implementation
1from string import ascii_lowercase
2
3class Solution:
4 def decodeMessage(self, key: str, message: str) -> str:
5 # Dictionary that maps each unique letter in 'key' to the corresponding letter in the alphabet
6 # Initial mapping for space character is included as it maps to itself
7 char_mapping = {" ": " "}
8
9 # Index to keep track of the next letter in the alphabet to be used for mapping
10 next_alpha_index = 0
11
12 # Iterate through each character in the 'key'
13 for char in key:
14 # Check if the character is not already in the mapping dictionary
15 if char not in char_mapping:
16 # Map the character to the next available letter in the alphabet
17 char_mapping[char] = ascii_lowercase[next_alpha_index]
18 # Move to the next letter in the alphabet
19 next_alpha_index += 1
20
21 # Convert the message using the generated mapping by replacing each character
22 # with its corresponding mapped character
23 decoded_message = "".join(char_mapping[char] for char in message)
24
25 return decoded_message
26
1class Solution {
2
3 // Decodes a message using a substitution cipher provided by the 'key'.
4 public String decodeMessage(String key, String message) {
5 // Array to hold the substitution cipher mapping.
6 char[] decoder = new char[128];
7 // Preserving the space character.
8 decoder[' '] = ' ';
9
10 // Initialize variables for tracking indices in 'key' and 'decoder'.
11 for (int keyIndex = 0, decoderIndex = 0; keyIndex < key.length(); ++keyIndex) {
12 // Get the current character from the key.
13 char currentChar = key.charAt(keyIndex);
14 // If current character is not already present in the 'decoder' array, add it.
15 if (decoder[currentChar] == 0) {
16 // Map the current character to the next available character in the alphabet.
17 decoder[currentChar] = (char) ('a' + decoderIndex++);
18 }
19 }
20
21 // Convert the message into a char array for in-place decoding.
22 char[] decodedMessage = message.toCharArray();
23
24 // Loop through the message and decode each character.
25 for (int messageIndex = 0; messageIndex < decodedMessage.length; ++messageIndex) {
26 // Substitute the character using the decoder array.
27 decodedMessage[messageIndex] = decoder[decodedMessage[messageIndex]];
28 }
29
30 // Return the decoded message as a string.
31 return String.valueOf(decodedMessage);
32 }
33}
34
1#include <string>
2using namespace std;
3
4class Solution {
5public:
6 string decodeMessage(string key, string message) {
7 // Create a dictionary to hold the character mapping.
8 // Initialize a lookup array to zero, assuming ASCII values.
9 char dictionary[128] = {};
10
11 // Map space to itself since it is not to be encoded.
12 dictionary[' '] = ' ';
13
14 // Start with the first lowercase letter for substitution.
15 char substitution_letter = 'a';
16
17 // Iterate through the key and fill the dictionary for encoding.
18 for (char& current_char : key) {
19 // Check if character is already mapped; if not, map it
20 if (!dictionary[current_char] && current_char >= 'a' && current_char <= 'z') {
21 dictionary[current_char] = substitution_letter++;
22 // Stop if all letters have been mapped
23 if(substitution_letter > 'z') break;
24 }
25 }
26
27 // Decode the message using the filled dictionary.
28 for (char& current_char : message) {
29 // Replace each character in the message with the mapped character.
30 current_char = dictionary[current_char];
31 }
32
33 // Return the decoded message.
34 return message;
35 }
36};
37
1// Function to decode a message using a substitution cipher provided by a key
2function decodeMessage(key: string, message: string): string {
3 // Dictionary to hold the key-value pairs for decoding
4 const decoderMap = new Map<string, string>();
5
6 // Loop through each character in the key to build the decoder map
7 for (const char of key) {
8 // If the character is a space or already exists in the map, skip it
9 if (char === ' ' || decoderMap.has(char)) {
10 continue;
11 }
12
13 // Map the character to its corresponding decoded alphabet
14 // The decoded character is determined by the current size of the decoder map
15 // 'a'.charCodeAt(0) converts the letter 'a' to its ASCII code,
16 // then the size of the decoderMap is added to get the new character
17 decoderMap.set(char, String.fromCharCode('a'.charCodeAt(0) + decoderMap.size));
18 }
19
20 // Ensure space is mapped to itself in the decoder map
21 decoderMap.set(' ', ' ');
22
23 // Transform the message: Split the message into characters, decode each character, and join the decoded characters
24 return [...message].map(char => decoderMap.get(char)).join('');
25}
26
Time and Space Complexity
The time complexity of the provided code is primarily determined by two operations: iterating through the key
string, and building the decoded message
string.
-
Iterating through the
key
string involves checking each character to see if it is already in the dictionaryd
. Each check is an O(1) operation due to the hash table underlying Python dictionaries. There are at most 26 unique letters to insert into the dictionary (ignoring spaces as they are hardcoded), so that part of the algorithm is O(26), which simplifies to O(1) since we ignore constants and non-dominant terms in Big O notation. -
Converting the
message
involves a single pass through the message characters, each look-up in the dictionaryd
is O(1), and we perform a constant time operation for each character in themessage
. Therefore, if the message length isn
, this part of the algorithm is O(n).
The combined time complexity is therefore O(n), where n
is the length of the message
, since this is the dominant term.
The space complexity is determined by the additional space used by the algorithm. Here, it is the space required to store the d
dictionary and the output string.
-
The dictionary
d
stores a mapping of characters to characters, and there are at most 26 letter mappings plus one space mapping, so it requires O(27) space, which simplifies to O(1). -
The space complexity for the output string is O(n), where
n
is the length of themessage
, because we're building a new string with the same length as the input message.
Therefore, the overall space complexity of the algorithm is O(n), where n
is the length of the message
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which type of traversal does breadth first search do?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!