Abstract / Summary

Check if a string and a word list have a one to one mapping where each word matches a unique pattern part.

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 44% (2+ million 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 wordPattern method determines whether a given string s follows the same pattern as the characters in pattern. It treats each character in pattern as a placeholder for a distinct word in s. The method builds a mapping from pattern characters to words, verifies that the mapping is consistent throughout the string, ensures that no two characters map to the same word, and finally checks that the entire input string has been consumed.

Parsing the Input String

The function uses a stringstream to extract words from s one by one. By feeding the whole string into the stream, the code can read space-separated tokens with the extraction operator (>>).

stringstream text;
text.str(s);

Mapping Pattern Characters to Words

For each character c in pattern, the code reads the next word from the stream. If the stream yields an empty word, the pattern cannot be satisfied and the function returns false. When a character has not been seen before, it is added to the map p with the current word as its value.

for (auto c : pattern)
{
    string word;
    text >> word;

    if (word.empty())
        return false;

    if (p.count(c) == 0)
    {
        p[c] = word;
        continue;
    }

    if (word != p[c])
        return false;
}

Verifying One-to-One Correspondence

After the initial pass, the map may contain multiple characters that point to the same word, which would violate the required bijection. The code iterates over the map entries and uses an unordered_set to detect duplicate word values. Encountering a duplicate causes an immediate false return.

unordered_set<string> u;
for (auto i : p)
{
    if (u.count(i.second) > 0)
        return false;
    u.insert(i.second);
}

Ensuring Complete Consumption of the Input

The final step checks that no extra words remain after processing all characters of pattern. By attempting to read one more token into x, the code confirms that the stream is exhausted; if x is non-empty, the input contains surplus words and the pattern does not match.

string x;
text >> x;
return x.empty();

Edge Cases Handled

The implementation gracefully handles several boundary conditions. When the input string contains fewer words than there are characters in the pattern, the extraction yields an empty string, triggering an early false. Conversely, if the string contains more words than the pattern length, the final stream read detects the leftover token and returns false. The duplicate-word detection step prevents two different pattern characters from mapping to the same word, covering the case where the pattern would otherwise appear to match but violates the one-to-one requirement. Additionally, an empty pattern with an empty string results in a successful match because the loop body never executes and the final stream read finds no extra tokens.

Performance Optimizations

The algorithm employs early exits to avoid unnecessary work. As soon as a mismatch is detected-whether due to a missing word, an inconsistent mapping, or a duplicate word-the function returns immediately, preventing further iteration. The use of unordered_set for duplicate detection provides average-case constant-time lookups, making the uniqueness check efficient even for larger inputs. Storing the mapping in a map allows logarithmic-time access for each character lookup, which balances the need for ordered storage with acceptable performance for typical input sizes. By processing the input string in a single pass and performing the uniqueness verification in a separate linear pass over the map, the overall work scales linearly with the length of the pattern and the number of distinct words.

Imagine you have a puzzle with little stickers and colored blocks. Each sticker has a special shape like a circle or a star on it. The task is to make sure every shape always matches up with the exact same color.

The code starts by getting a list of stickers and a pile of blocks. It looks at the first sticker and says that this shape must belong to the first block it finds. It keeps a notebook to write down which shape goes with which color. If it sees a shape that is already in the notebook, it checks the pile to see if the block is the right color. If the color is different, the puzzle is broken, so it stops.

After checking all the stickers, it does one more important job. It looks through the notebook to make sure every single shape is matched to a different color. If two different shapes are trying to claim the same color block, that is not allowed either. Finally, it makes sure there are no leftover blocks sitting in the pile. If every sticker has a perfect match and nobody is left over, the puzzle is solved correctly.

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

not analyzed yet

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	C++	Python	Java								TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	C#	Rust				Go		TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei					Rust
	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	everthis						JS
	fartem								Ruby
	fengvyi	C++
	halfrost									Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	lennylxx	C++
	linouk23	C++
	lkwq007		Python
	martianoff							Scala
	pruthvikp		Python
	qiyuangong		Python
	ruoru					Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vli02										C
	vthwang			Java
	XiaotaoGuo	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C++
linouk23	C++
lkwq007	Python
martianoff	Scala
pruthvikp	Python
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
YuriSpiridonov	Python
zfang399	C++

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