Leetcode 2325: Decode the Message

Input: The input consists of two strings: key, representing the cipher key, and message, representing the secret message to decode.

Example: key = "jumping over hills in the park", message = "swm tlnh dbe"

Constraints:

• The key will contain all 26 lowercase English letters at least once.

• The key may contain spaces, but they are ignored for decoding purposes.

• 1 <= message.length <= 2000

Output: Return the decoded message by applying the substitution table derived from the key.

Example: For key = "jumping over hills in the park" and message = "swm tlnh dbe", the output is "the quick fox".

Constraints:

• The decoded message should be returned as a string.

Goal: To decode the message using the substitution table derived from the key.

Steps:

• 1. Create a substitution table based on the first occurrence of each letter in the key.

• 2. Replace each letter in the message with the corresponding letter from the substitution table.

• 3. Return the decoded message, ensuring spaces remain unchanged.

Goal: The key string contains at least one occurrence of each letter from 'a' to 'z'. The message string consists of lowercase English letters and spaces.

Steps:

• 1 <= message.length <= 2000

• The key contains every letter from 'a' to 'z' at least once.

Assumptions:

• The key is a valid string of lowercase English letters containing all letters from 'a' to 'z'.

• The message is also valid, containing only lowercase English letters and spaces.

• Input: key = "jumping over hills in the park", message = "swm tlnh dbe"

• Explanation: Using the first occurrence of each letter in the key as a substitution table, we decode 'swm tlnh dbe' to 'the quick fox'.

• Input: key = "smart minds solve problems", message = "jqjc bmcms wbs"

• Explanation: Using the first occurrence of each letter in the key as a substitution table, we decode 'jqjc bmcms wbs' to 'the code works'.

Approach: The problem can be solved by creating a substitution table from the cipher key and applying it to decode the message.

Observations:

• We need to map each letter from the key to the alphabet using its first occurrence.

• This substitution table can then be applied to decode the message.

• We can use a simple mapping approach to replace each character in the message based on the substitution table.

Steps:

• 1. Initialize a mapping array to store the substitution for each letter from 'a' to 'z'.

• 2. Traverse the key to create the substitution mapping based on the first appearance of each character.

• 3. Iterate through the message and replace each character using the substitution mapping. Maintain spaces unchanged.

• 4. Return the decoded message.

Empty Inputs:

• The problem guarantees a non-empty message, so no need to handle empty inputs.

Large Inputs:

• The solution must handle message lengths up to 2000 efficiently.

Special Values:

• Key strings may have multiple spaces, which should be ignored when forming the substitution table.

Constraints:

• The message string will always have valid characters (lowercase letters and spaces).

string decodeMessage(string key, string mess) {
    char m[128] = {}, cur = 'a';
    for (char k : key)
        if (isalpha(k) && m[k] == 0)
            m[k] = cur++;
    for (int i = 0; i < mess.size(); ++i)
        mess[i] = m[mess[i]] ?: mess[i];
    return mess;
}

1 : Function Declaration

string decodeMessage(string key, string mess) {

Declare the `decodeMessage` function, which takes two arguments: `key` (the mapping key) and `mess` (the message to decode). The function will return the decoded message.

2 : Character Array Initialization

    char m[128] = {}, cur = 'a';

Initialize a character array `m[128]` to store the mappings for the characters. The variable `cur` is initialized to 'a' to start the mapping from 'a'.

3 : Key Iteration

    for (char k : key)

Loop through each character `k` in the `key` string.

4 : Character Mapping Check

        if (isalpha(k) && m[k] == 0)

Check if the character `k` is alphabetic and if it has not already been mapped (i.e., `m[k] == 0`).

5 : Character Mapping

            m[k] = cur++;

If the character `k` is alphabetic and not yet mapped, assign it the next available letter in the alphabet (starting from 'a') and increment `cur`.

6 : Message Decoding Loop

    for (int i = 0; i < mess.size(); ++i)

Loop through each character in the message `mess` and apply the character mapping to decode the message.

7 : Character Replacement

        mess[i] = m[mess[i]] ?: mess[i];

For each character in the message, replace it with the mapped character from `m` if a mapping exists. If no mapping exists (i.e., the character is not in `key`), retain the original character.

8 : Return Statement

    return mess;

Return the decoded message after all characters have been processed.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the length of the message, as we need to iterate through both the key and the message once.

Best Case: O(26 + n)

Worst Case: O(26 + n)

Description: The space complexity is O(26 + n), where 26 accounts for the mapping and n is the space required for the decoded message.

Leetcode 2325: Decode the Message

Explore →