Abstract / Summary

Find the least number of operations to change one word into another using insert delete or replace.

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 61% (2+ million submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• 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 solves the classic regular-expression matching problem where the pattern may contain the wildcard “.” (matching any single character) and the quantifier “*” (matching zero or more occurrences of the preceding element). The solution is organized as a class with three memoized helper methods-dot, star, and match-and a public entry point isMatch. Each helper focuses on a specific syntactic construct, allowing the main matcher to delegate responsibility and keep the recursion depth manageable.

dot

The dot method handles the case where the current pattern token is a dot. It first checks for an empty pattern, returning true only when the remaining text consists of a single character, which aligns with the semantics of a solitary dot. When the next pattern character is a star, the method iterates from the longest possible suffix of text down to the empty string, invoking match on each candidate. This “longest-first” strategy ensures that the first successful match short-circuits further exploration. If the pattern does not start with a star, the method verifies that text is non-empty and then recurses on the remainder of both strings.

@cache
def dot(self, text, pattern):
    if not pattern:
        return len(text) == 1
    if pattern[0] == "*":
        for i in range(len(text), -1, -1):  # longest first
            if self.match(text[i:], pattern[1:]):
                return True
        return False

    if not text:
        return False

    return self.match(text[1:], pattern)

star

The star method implements the semantics of the “*” quantifier for a specific preceding literal letter. It first counts how many consecutive characters at the start of text match letter. The loop that follows then attempts to match the remaining pattern against progressively shorter prefixes of text, again starting with the longest possible match. By trying the longest prefix first, the algorithm reduces the number of recursive calls needed when a match exists early in the search space.

@cache
def star(self, text, pattern, letter):
    same = 0
    while same < len(text) and text[same] == letter:
        same += 1

    # longest first to reduce recursion
    while same >= 0:
        if self.match(text[same:], pattern):
            return True
        same -= 1
    return False

match

The match method is the central dispatcher. It first handles the base case of an empty pattern, succeeding only when the input text is also empty. When the pattern begins with a dot, it delegates to dot with the remainder of the pattern. If a star follows a literal (detected by checking pattern[1] == "*") the method forwards control to star, passing the literal and the pattern after the quantifier. For ordinary literal characters, the method walks forward while the characters of text and pattern are identical, stopping at the first mismatch or when either string ends. A subtle adjustment is made when a star follows the matched segment: the index is decremented to include the preceding literal in the subsequent recursive call. If no characters match at all, the method returns false; otherwise it recurses on the unmatched suffixes of both strings.

@cache
def match(self, text, pattern):
    if not pattern:
        return not text

    if pattern[0] == ".":
        return self.dot(text, pattern[1:])

    if len(pattern) >= 2 and pattern[1] == "*":
        return self.star(text, pattern[2:], pattern[0])

    if not text:
        return False

    i = 0
    while i < len(pattern) and i < len(text) and pattern[i] == text[i]:
        i += 1

    if i > 0 and i < len(pattern) and pattern[i] == "*":
        i -= 1

    if i == 0:
        return False
    return self.match(text[i:], pattern[i:])

isMatch

The public method isMatch simply forwards the supplied strings to match. Because all recursive helpers are memoized, repeated sub-problems encountered during the depth-first search are resolved instantly from the cache, guaranteeing deterministic performance for overlapping sub-structures.

def isMatch(self, s: str, p: str) -> bool:
    return self.match(s, p)

Edge Cases Handled

The implementation explicitly addresses several boundary conditions. An empty pattern succeeds only when the input text is also empty, preventing false positives when the pattern is exhausted prematurely. When the pattern consists solely of a dot, the code checks that exactly one character remains in the text, ensuring correct handling of single-character wildcards. The dot method also treats a leading star in the pattern by iterating over all possible split points, thereby covering the scenario where the star quantifier applies to an implicit empty preceding element. The star helper safely handles the case where the preceding literal does not appear at the start of text by initializing the count to zero and immediately attempting a match with the unchanged text. The main matcher guards against accessing pattern[1] when the pattern length is one, avoiding index errors. Finally, when the input text becomes empty before the pattern, the code returns false unless the remaining pattern can legally match an empty string (e.g., a star quantifier), which is naturally handled by the star routine.

Performance Optimizations

Memoization is the cornerstone of the performance strategy. By decorating dot, star, and match with @cache, the algorithm stores the result of each unique (text, pattern) pair. This eliminates exponential blow-up typical of naïve recursive regular-expression engines, as repeated sub-problems are resolved in constant time after their first computation. The loops in both dot and star are deliberately ordered from longest to shortest suffix or prefix. This “longest-first” ordering often discovers a successful match early, allowing the function to return without exploring shorter alternatives. The early-return checks-such as verifying that text is non-empty before recursing on a literal match-prevent unnecessary recursive descent. The incremental scan in match that advances while characters are equal reduces the number of recursive calls by collapsing contiguous literal matches into a single step. Together, these techniques keep the recursion depth shallow for typical inputs and ensure that the algorithm scales gracefully with pattern complexity.

Imagine having a big pile of letter blocks and a special set of rules for how to build a word. The code acts like a very careful helper that checks if the word you made follows those specific rules.

There are three special helpers working together. The match helper acts like a detective. It looks at the very first letter of the word and the first piece of the rule to see if they match. If the rule says a letter is a simple character like an 'a', the helper checks if the word starts with an 'a'.

Sometimes a rule has a dot. The dot is a magical placeholder that can be any letter you want it to be. When the detective sees a dot, it hops over to the dot helper to see if the rest of the letters fit the remaining rules.

Other times a rule has a star. The star is extra fun because it means the letter before it can be used zero times, one time, or many times in a row. The star helper is like someone trying on different hats. It tries using the letter a bunch of times, then tries using it a little less, and keeps trying until it finds a way that works or runs out of options.

Finally, the code puts all these tiny checks together. It stares at the word and the rule, breaking them down bit by bit. It keeps moving forward through the letters and the instructions until everything is cleared or until it figures out the pattern is just not going to work.

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++	Python					Java		TS
	WalkCCC	C++	Python					Java
	leetcode.ca	C++	Python				JS	Java	Go	TS
	LeetcodeHelp	C++	Python					Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python					Java
github	aylei					Rust
	begeekmyfriend				C
	BigEggStudy			C#
	black-shadows		Python
	chandansgowda		Python
	charles-wangkai							Java
	chenyanzhe	C++
	everthis						JS
	FelixFan1122			C#
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	lennylxx				C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	lzl124631x	C++
	MacJim	C++
	qiyuangong		Python
	ruoru					Rust
	sonugiri1043	C++
	suxrobGM			C#
	trung-hn		Python
	varunu28							Java
	vli02				C
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	Python, Python
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
FelixFan1122	C#
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
lzl124631x	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	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