algoadvance

Leetcode 2325. Decode the Message

Problem Statement

You are given a string key and a string message which has been encoded using a substitution cipher based on the key. Find the original decoded message.

To decode the message:

Clarifying Questions

  1. What should I do with characters in message that aren’t present in key?
    • All characters in the message that are not letters should remain unchanged in the output.
  2. Are both key and message guaranteed to be in lowercase?
    • Yes, both key and message are given in lowercase.
  3. What if key is shorter than the English alphabet or doesn’t contain all 26 letters?
    • It is assumed that key will contain at least all the letters required to decode the message properly.

Strategy

  1. Create a mapping from the key: Iterate through each character in the key and build a mapping to the 26 lowercase English letters in order. Ensure that duplicates are ignored.
  2. Decode the message: Using the mapping from the previous step, replace each character in the message with its corresponding mapped character, leaving non-letter characters unchanged.
  3. Return the decoded message: After processing the entire message, return the decoded version.

Code

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>

std::string decodeMessage(const std::string& key, const std::string& message) {
    std::unordered_map<char, char> mapping;
    std::unordered_set<char> seen;
    char currentChar = 'a';

    // Create the mapping from the key
    for (char c : key) {
        if (c >= 'a' && c <= 'z') {
            if (seen.find(c) == seen.end()) {
                mapping[c] = currentChar;
                currentChar++;
                seen.insert(c);
            }
        }
    }

    // Decode the message
    std::string decodedMessage;
    decodedMessage.reserve(message.size());

    for (char c : message) {
        if (c >= 'a' && c <= 'z') {
            decodedMessage += mapping[c];
        } else {
            decodedMessage += c;
        }
    }

    return decodedMessage;
}

int main() {
    std::string key = "the quick brown fox jumps over the lazy dog";
    std::string message = "vkbs bs t suepuv";
    std::string decodedMessage = decodeMessage(key, message);
    std::cout << "Decoded Message: " << decodedMessage << std::endl;
    return 0;
}

Time Complexity

Overall, the time complexity is O(N + M), which is efficient for this problem.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI