Abstract / Summary

Check if each dictionary word can be changed to a query word with at most two character edits.

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 73% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• String
• Trie

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 Solution class implements a method twoEditWords that receives a list of query strings and a list representing a dictionary. Its purpose is to return, for each query, the first dictionary word that differs by at most two characters. The implementation removes duplicate dictionary entries, then iterates through each query and performs a character-by-character comparison with every dictionary word until a suitable match is found. When a match is identified, the query itself is yielded as part of the result sequence, and the inner loop stops early.

Key Steps

Removing duplicate dictionary entries

dictionary = set(dictionary)

By converting the incoming list to a set, the code eliminates repeated words. This reduction in the number of elements that need to be examined directly lowers the amount of work performed in the subsequent nested loops.

Iterating over queries

for q in queries:

The outer loop processes each query string in the order supplied. The method treats each query independently, resetting the search state for every new query.

Scanning the dictionary for a close match

for d in dictionary:

For each query, the inner loop walks through the deduplicated dictionary. The loop is designed to stop as soon as a word meeting the edit distance condition is found, preventing unnecessary comparisons with the remaining dictionary entries.

Counting character differences with early exit

diff = 0
for a, b in zip(q, d):
    if a != b:
        diff += 1
        if diff > 2:
            break

The code aligns the characters of the query and dictionary word using zip, which stops at the length of the shorter string. It increments a counter each time a mismatch occurs. An early-exit break is triggered the moment the counter exceeds two, which avoids further work on pairs that are already disqualified.

Yielding a matching query

if diff <= 2:
    yield q
    break

When the difference count remains within the allowed threshold, the query string is emitted via yield. The subsequent break exits the dictionary loop, ensuring that only the first qualifying dictionary word influences the output for that query.

Edge Cases Handled

The algorithm naturally accommodates queries and dictionary words of differing lengths because zip truncates to the shorter of the two strings. In such situations, any extra characters in the longer word are ignored for the purpose of counting mismatches, effectively treating them as matching up to the length of the shorter word. If a query is an empty string, the inner loop still executes, and the difference count stays at zero, causing the empty query to be yielded immediately if the dictionary contains any entry. Conversely, if the dictionary is empty after deduplication, the outer loop completes without yielding any values, resulting in an empty generator output.

Performance Optimizations Observed

The conversion of the dictionary list to a set eliminates duplicate entries, which reduces the number of inner-loop iterations. The early-exit condition inside the character comparison loop prevents the algorithm from scanning the entire length of a word once it is clear that the edit distance exceeds two. Additionally, the break after a successful match stops further dictionary scans for the current query, ensuring that only the minimal necessary work is performed per query. These strategies collectively keep the runtime proportional to the number of queries multiplied by the number of distinct dictionary words that must be examined before a match is found.

Imagine you have a big bag of words and a list of secret words you are trying to guess. The computer starts by taking all the words in the bag and putting them into a neat pile where every word is unique. Then it looks at the first word from the guessing list and picks up one word from the bag to check if they are almost the same. It looks at the letters one by one in both words. Every time it finds a letter that is different, it keeps a little tally. If it finds more than two differences, it stops looking at that pair because the words are too far apart. But if it finds that the words have two or fewer differences, it remembers that word as a match and moves on to the next word from the guessing list. The computer repeats this process until it has checked every word it needs to look at.

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

Time: polynomial
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	C++		Java			Python		TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++		Java	C#	Go	Python	Rust	TS
	Progiez	C++		Java			Python
github	charles-wangkai			Java
	fsq	C++
	JoshCrozier		JS
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
withaarzoo	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