Decode the Message
Problem
You are given a string key and a string message. The first appearance of every one of the 26 lowercase letters in key (ignoring spaces) forms a substitution table: that letter maps to 'a', the next new letter to 'b', and so on. Decode message by replacing each letter with its mapped value; spaces stay as spaces.
key = "the quick brown fox jumps over the lazy dog", message = "vkbs""this"def decode_message(key, message):
table = {}
nxt = ord('a')
for ch in key:
if ch != ' ' and ch not in table:
table[ch] = chr(nxt)
nxt += 1
return "".join(table.get(c, ' ') for c in message)function decodeMessage(key, message) {
const table = {};
let nxt = 0;
for (const ch of key) {
if (ch !== ' ' && !(ch in table)) {
table[ch] = String.fromCharCode(97 + nxt);
nxt++;
}
}
let out = "";
for (const c of message) out += c === ' ' ? ' ' : table[c];
return out;
}class Solution {
public String decodeMessage(String key, String message) {
char[] table = new char[128];
char nxt = 'a';
for (char ch : key.toCharArray()) {
if (ch != ' ' && table[ch] == 0) {
table[ch] = nxt++;
}
}
StringBuilder out = new StringBuilder();
for (char c : message.toCharArray())
out.append(c == ' ' ? ' ' : table[c]);
return out.toString();
}
}string decodeMessage(string key, string message) {
char table[128] = {0};
char nxt = 'a';
for (char ch : key) {
if (ch != ' ' && table[(int)ch] == 0) {
table[(int)ch] = nxt++;
}
}
string out = "";
for (char c : message)
out += (c == ' ') ? ' ' : table[(int)c];
return out;
}Explanation
This is a substitution cipher. The trick is that the cipher alphabet is defined by the order in which new letters first show up in key: the first distinct letter decodes to 'a', the second distinct letter to 'b', and so on through the alphabet.
So we scan key once, keeping a table (a hash map, or just a 128-slot array) and a counter nxt that starts at 'a'. Whenever we meet a letter we have not seen before (and it is not a space), we assign it the current nxt and bump nxt to the next letter.
Spaces are ignored while building the table — they are not letters and carry no mapping.
Once the table is built, decoding is a straight pass over message: each letter is replaced by table[c], and every space is copied through unchanged. Because the first 26 distinct letters of any valid key cover the whole alphabet, every letter in the message is guaranteed to have a mapping.
Example: from "the quick brown fox jumps over the lazy dog" we get t→a, h→b, e→c, q→d, u→e, ..., and further along v→t, k→h, b→i, s→s. Decoding "vkbs" letter by letter yields "this".