Weekly Contest 300 | Leetcode 2325 Decode the Message | Easy DP
Decode the Message - Video Solution
Watch 10 video solutions for Decode the Message, a easy level problem involving Hash Table, String. This walkthrough by Coding Decoded has 3,898 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given the strings key and message, which represent a cipher key and a secret message, respectively. The steps to decode message are as follows:
- Use the first appearance of all 26 lowercase English letters in
keyas the order of the substitution table. - Align the substitution table with the regular English alphabet.
- Each letter in
messageis then substituted using the table. - Spaces
' 'are transformed to themselves.
- For example, given
key = "happy boy"(actual key would have at least one instance of each letter in the alphabet), we have the partial substitution table of ('h' -> 'a','a' -> 'b','p' -> 'c','y' -> 'd','b' -> 'e','o' -> 'f').
Return the decoded message.
Example 1:
Input: key = "the quick brown fox jumps over the lazy dog", message = "vkbs bs t suepuv" Output: "this is a secret" Explanation: 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" Explanation: The diagram above shows the substitution table. It is obtained by taking the first appearance of each letter in "eljuxhpwnyrdgtqkviszcfmabo".
Constraints:
26 <= key.length <= 2000keyconsists of lowercase English letters and' '.keycontains every letter in the English alphabet ('a'to'z') at least once.1 <= message.length <= 2000messageconsists of lowercase English letters and' '.
Approach Overview
Problem Overview: You receive a key string representing a substitution cipher and a message string encoded with that cipher. The first appearance of each character in key maps sequentially to the alphabet (a to z). Spaces stay unchanged. The task is to reconstruct the mapping and decode the original message.
Approach 1: HashMap for Character Mapping (O(n) time, O(1) space)
This approach builds the substitution table explicitly using a hash table. Iterate through the key from left to right and assign each new character to the next unused letter in the alphabet. Skip spaces and ignore characters already mapped. Once the mapping is built, iterate through the message and replace each character using constant-time hash lookups. Spaces are copied directly. Since the alphabet size is fixed at 26, the hash table remains small and effectively constant space.
The key insight: the cipher order is determined by the first occurrence of characters in the key. A hash map makes it trivial to check whether a character has already been assigned and to retrieve its mapped value instantly. This approach is clean, readable, and works naturally with most programming languages.
Approach 2: Character Array Substitution (O(n) time, O(1) space)
This method replaces the hash table with a fixed-size array of length 26. Each index represents a letter (index = char - 'a') and stores its mapped value. While scanning the key, fill the array whenever you encounter a character that has not yet been assigned. Track the next available alphabet character and advance it as mappings are created.
Decoding works by iterating through the message and performing direct array lookups. This avoids hashing overhead and relies purely on arithmetic indexing. The logic is essentially the same as the hash map solution, but with a slightly lower constant factor.
Because the alphabet size is fixed, the substitution array consumes constant memory and guarantees O(1) access time. Problems involving character substitution or frequency counting often benefit from this pattern when working with string data and small character sets.
Recommended for interviews: The hash map solution is typically expected because it clearly demonstrates understanding of substitution mapping and efficient lookups. The array-based version is a small optimization that shows awareness of constant-factor improvements and fixed alphabet constraints. Both run in O(n) time where n is the length of the key plus the message.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap for Character Mapping | O(n) | O(1) | General approach. Clear and easy to implement in interviews using a hash table. |
| Character Array Substitution | O(n) | O(1) | When optimizing constant factors or working with fixed lowercase alphabets. |