Abstract / Summary

Given a coded string using digits to represent letters A to I, return the decoded message using a to i mapping.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 86% (100k+ submissions).

Typical patterns to solve this problem:

• Hash Table
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single method decodeMessage. The method receives two strings: key, which supplies a substitution cipher, and message, the text to be decoded. The core idea is to construct a mapping from each distinct character in key to successive letters of the English alphabet, preserving spaces, and then translate message using that mapping.

Key Steps

The first important step is the initialization of the substitution dictionary. The code creates a dictionary called mapping that already contains an entry for the space character, mapping it to itself. This ensures that whitespace is retained unchanged during decoding.

mapping = { " ": " " }

Next, a variable named next is set to the character 'a'. This variable tracks the next alphabetic character to assign in the mapping.

next = "a"

The method then iterates over each character k in the key string. For every character that has not yet been added to mapping, the code assigns the current value of next as its substitution and then advances next to the following alphabetic character by converting it to its Unicode code point, incrementing, and converting back to a character.

for k in key:
    if k not in mapping:
        mapping[k] = next
        next = chr(ord(next) + 1)

After the mapping is fully built, the method constructs the decoded output. It does this by joining together the mapped values for each character c in message. The generator expression mapping[c] for c in message looks up each character directly in the dictionary, guaranteeing O(1) access per character.

return "".join(mapping[c] for c in message)

Edge Cases Handled

The code explicitly includes a mapping for the space character, which means any spaces present in message are reproduced verbatim in the output. This handling prevents a KeyError that would otherwise occur if a space appeared in message but was not present in key.

Because the mapping is built only from characters that appear in key, any character in message that does not exist in key (other than space) would raise an exception. However, the problem specification guarantees that message contains only characters that are present in key or spaces, so the implementation safely assumes the lookup will always succeed.

The iteration over key uses a simple containment check (if k not in mapping). This ensures that repeated characters in key do not cause the mapping to be overwritten, preserving the first occurrence's assignment. Consequently, the cipher respects the order of first appearance, which is essential for a deterministic decoding.

Performance Optimizations

The construction of the mapping leverages a dictionary, providing constant-time insertion and lookup. By checking if k not in mapping before insertion, the code avoids unnecessary assignments for duplicate characters, reducing the number of operations proportional to the length of key.

The use of chr(ord(next) + 1) to advance the substitution character is a lightweight arithmetic operation that avoids more complex data structures or look-up tables. Because the alphabet is traversed sequentially, the code does not need to compute the position of each character repeatedly.

Finally, the decoding step uses a generator expression inside str.join. This pattern builds the result string in a single pass without creating intermediate lists, minimizing memory overhead and taking advantage of the efficient concatenation logic of str.join.

Imagine you have a secret code made of letters. Usually, a is the first letter, b is the second, and so on. This code uses a special key to mix everything up.

Think of this code like a magical translator machine. First, it looks at the key you provided. It starts with the letter a and gives it a new secret identity based on the first letter it finds in the key. Then it moves to the next letter, b, and gives it the secret identity of the second letter in the key. It keeps doing this until all the letters from the key have a new secret partner.

The machine remembers these secret partners in a little list. Once it has finished reading the whole key, it looks at the message you want to decode. For every letter in that message, it looks at its little list to find the secret partner. It takes that partner and builds a brand new message, piece by piece, until the secret is finally revealed.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python		Java		C++				TS
	WalkCCC	Python		Java		C++
	leetcode.ca	Python		Java		C++	C	Go	Rust	TS
	Progiez	Python		Java		C++
github	chandansgowda	Python
	charles-wangkai			Java
	DimitrisJim						C
	everthis		JS
	fartem				Ruby
	fsq					C++
	JoshCrozier		JS
	lkwq007	Python
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality