2325. Decode the Message

EasyHash TableString

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 variable i 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 a for loop. For each character c found in key, 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 the i-th letter from the English alphabet (contained in the string module from Python's standard library). The variable i is incremented only when a new mapping is created. This ensures that each unique letter in key 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 dictionary d 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 Evaluator

Example 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 dictionary d.
- Our dictionary starts as d = {" ": " "}.
Iterating through the key:
- The first character is t, which is not in d, so we add it: d = {" ": " ", "t": "a"}.
- The second character is h, not in d 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.
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.
Message Decoding:
- Now, we decode the message by looking at each character and using our dictionary d 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 from d.
Resulting Output:
- After applying the substitution to each character, we get the final message: "this is a super"
- The message has been successfully decoded!

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 dictionary d. 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 dictionary d is O(1), and we perform a constant time operation for each character in the message. Therefore, if the message length is n, 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 the message, 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following shows the order of node visit in a Breadth-first Search?

I don’t know