Python 0115.py
class Solution:
def numDistinct(self, s: str, t: str) -> int:
@cache
def deeper(posS, posT):
if posT == len(t):
return 1 # match
if posS == len(s):
return 0 # incomplete
if s[posS] == t[posT]:
return deeper(posS + 1, posT + 1) + deeper(posS + 1, posT) # consume letter or skip letter
else:
return deeper(posS + 1, posT) # need to skip letter
result = deeper(0, 0)
if result >= 2**31: # ??? weird test case, requires -1 if result is too large
result = -1
return result
Difficulty
and has an acceptance rate of about 52% (1+ million submissions).
Typical patterns to solve this problem:
- Dynamic Programming
- String
AI Disclaimer
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.
Code Walkthrough
Overview
The provided implementation solves the classic “distinct subsequences” problem: given two strings s and t, it counts how many ways t can be formed by deleting characters from s while preserving order. The solution is expressed as a depth-first recursion with memoization, which systematically explores the decision at each character of s to either match it with the current character of t or skip it. A final guard converts results that exceed a 32-bit signed integer limit into -1.
Recursive Structure
The core of the algorithm is the nested function deeper(posS, posT). It receives two indices: posS points to the current character in s, and posT points to the current character in t. The function returns the number of distinct ways the suffix t[posT:] can be matched using the suffix s[posS:].
@cache
def deeper(posS, posT):
...
The @cache decorator automatically stores previously computed results, turning the exponential recursion into a polynomial-time dynamic programming solution.
Base Cases
Two termination conditions are checked first:
- When
posTreaches the length oft, the entire target string has been matched. The function returns1, representing a single successful construction. - When
posSreaches the length ofswhileposThas not, there are no remaining characters to consume, so the function returns0.
if posT == len(t):
return 1 # full match achieved
if posS == len(s):
return 0 # source exhausted without completing match
These base cases correctly handle the situation where the target is empty (always one match) and where the source is exhausted prematurely.
Transition Logic
When both indices are within bounds, the algorithm decides based on character equality:
- If
s[posS]equalst[posT], two recursive branches are taken:- Advance both indices, consuming the matching character.
- Advance only
posS, skipping the character inswhile keeping the target position unchanged. The sum of these branches yields the total count for the current state.
if s[posS] == t[posT]:
return deeper(posS + 1, posT + 1) + deeper(posS + 1, posT)
- If the characters differ, the only viable action is to skip the current character of
sand continue searching.
else:
return deeper(posS + 1, posT)
This dichotomy ensures that every possible subsequence alignment is explored exactly once.
Result Post-Processing
After the recursive exploration finishes, the top-level call deeper(0, 0) yields the total number of distinct subsequences. The code then checks whether this total exceeds the 32-bit signed integer range (2**31). If it does, the specification demands returning -1 instead of the raw count.
result = deeper(0, 0)
if result >= 2**31:
result = -1
return result
This guard handles extreme inputs where the combinatorial explosion would otherwise produce a value that cannot be represented in a 32-bit signed integer.
Memoization and Caching
The use of @cache (available from Python 3.9 onward) is the primary performance optimization. By caching the result of each (posS, posT) pair, the algorithm avoids recomputing identical subproblems. The recursion tree collapses into a directed acyclic graph whose nodes correspond to unique index pairs. Consequently, each state is evaluated once, and the total number of states is bounded by len(s) * len(t). The cache also implicitly provides fast lookup for previously solved sub-instances, turning the naive exponential recursion into a dynamic programming solution with deterministic execution time.
Edge Cases Handled
The implementation gracefully handles several edge conditions:
- Empty target string: When
tis empty, the base caseposT == len(t)triggers immediately, returning1. This reflects the mathematical fact that there is exactly one way to form an empty subsequence (by deleting all characters). - Empty source string with non-empty target: The second base case returns
0, indicating that a non-empty target cannot be formed from an empty source. - Identical source and target: The recursion will match each character and progress both indices together, ultimately reaching the full-match base case, yielding a count of
1. - Source shorter than target: The recursion will exhaust
sbeforetcan be fully matched, causing the second base case to fire and propagate0up the call stack. - Large combinatorial counts: The final guard for values
>= 2**31ensures that the function complies with the requirement to return-1for overflow scenarios, preventing unintended large integer returns.
Performance Optimizations
Beyond memoization, the code benefits from the following implicit optimizations:
- Tail-call avoidance: By returning the sum of two recursive calls only when characters match, the algorithm minimizes unnecessary recursion depth for mismatched characters, directly proceeding to the next source index.
- Early termination: The base case for a fully matched target (
posT == len(t)) stops further recursion as soon as a valid subsequence is found, preventing wasteful exploration of remaining source characters. - Cache locality: Since the cache keys are simple integer tuples, Python’s built-in dictionary implementation provides fast hashing and retrieval, contributing to low overhead per memoized lookup.
Overall, the combination of a clear recursive formulation, exhaustive base case handling, and built-in memoization yields an implementation that is both conceptually straightforward and computationally efficient for the problem domain.
ELI5 - Simplified Explanation
Imagine there is a big pile of letter blocks laid out in a long row called s. There is also a smaller list of blocks called t that spells out a secret word. The goal is to figure out how many different ways those secret blocks can be picked out from the long row while keeping them in the exact same order.
The code works by looking at the blocks one by one. It starts by looking at the very first letter of the row and the first letter of the secret word. If the letters match, there is an exciting choice. It can use that letter to help spell the secret word, or it can leave that letter behind and keep looking for a match further down the row. If the letters do not match, it has to move on to the next block in the long row to keep hunting for the right one.
This process keeps repeating, always exploring both possibilities whenever a match is found. Because this could take a very long time, the code remembers the answers it has already figured out to save time later. Think of it like a map that keeps track of where it has already been. Finally, the code adds up all the different successful ways it found to spell the secret word. If the number of ways is truly massive, it just keeps track of that special case.
Code Quality
Complexity Analysis
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
Other Solutions
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 | Rust | Java | Go | TS | |||||
| LeetcodeHelp | C++ | Python | Java | ||||||||
| MemoryLimitExceeded | C++ | Python | |||||||||
| Progiez | C++ | Python | Java | ||||||||
| github | aylei | Rust | |||||||||
| begeekmyfriend | C | ||||||||||
| BigEggStudy | C# | ||||||||||
| black-shadows | Python | ||||||||||
| charles-wangkai | Java | ||||||||||
| chenyanzhe | C++ | ||||||||||
| everthis | JS | ||||||||||
| fartem | Ruby | ||||||||||
| fpdjsns | C++ | ||||||||||
| gaosq0604 | Python | ||||||||||
| Garvit244 | Python | ||||||||||
| gouthampradhan | Java | ||||||||||
| halfrost | Go | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JS | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| lennylxx | C | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| luangong | C++ | ||||||||||
| MacJim | C++ | ||||||||||
| qiyuangong | Python | ||||||||||
| ruoru | Rust | ||||||||||
| suxrobGM | C# | ||||||||||
| trung-hn | Python | ||||||||||
| wisdompeak | C++ | ||||||||||
| zfang399 | C++ | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++, Python, Java | ||||||||||
| leetcode.ca | C++, Go, Java, Python, Rust, TypeScript | ||||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||||
| MemoryLimitExceeded | Python, C++ | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| aylei | Rust | ||||||||||
| begeekmyfriend | C | ||||||||||
| BigEggStudy | C# | ||||||||||
| black-shadows | Python, Python | ||||||||||
| charles-wangkai | Java | ||||||||||
| chenyanzhe | C++ | ||||||||||
| everthis | JavaScript | ||||||||||
| fartem | Ruby | ||||||||||
| fpdjsns | C++ | ||||||||||
| gaosq0604 | Python | ||||||||||
| Garvit244 | Python | ||||||||||
| gouthampradhan | Java | ||||||||||
| halfrost | Go | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| lennylxx | C | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| luangong | C++ | ||||||||||
| MacJim | C++ | ||||||||||
| qiyuangong | Python | ||||||||||
| ruoru | Rust | ||||||||||
| suxrobGM | C# | ||||||||||
| trung-hn | Python | ||||||||||
| wisdompeak | C++ | ||||||||||
| zfang399 | C++ |
Videos
Solved On The Same Day
- problem 101: Symmetric Tree
- problem 337: House Robber III
- problem 790: Domino and Tromino Tiling
- problem 1035: Uncrossed Lines
- problem 124: Binary Tree Maximum Path Sum
Extra
- 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