# Recursion and Memoization Interview Patterns: LCS, Edit Distance, Word Break

Source: https://www.techinterview.org/post/3233462510/recursion-memoization-interview-patterns/
Updated: 2026-04-17 · techinterview.org

## Recursion and Memoization Interview Patterns

Memoization transforms exponential recursive solutions into polynomial ones by caching subproblem results. In Python, `@lru_cache` makes memoization trivial. This guide covers the patterns for recognizing when memoization applies and the most important problems.

## When Memoization Applies

Memoization works when a problem has:

- **Overlapping subproblems**: the same subproblem is computed multiple times in a naive recursion

- **Optimal substructure**: the optimal solution to a problem can be constructed from optimal solutions to subproblems

Signs you should memoize: the recursive tree has exponential branching (2^n calls) but only polynomial distinct states (n^2 distinct (i, j) pairs).

## Python Memoization with lru_cache


```
from functools import lru_cache

@lru_cache(maxsize=None)   # unlimited cache
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)
# Without cache: O(2^n) calls. With cache: O(n) unique calls.
```

For problems with mutable arguments (lists, dicts), convert to tuples before passing to cached functions.

## Coin Change (LeetCode 322)


```
def coin_change(coins, amount):
    @lru_cache(maxsize=None)
    def dp(remaining):
        if remaining < 0: return float('inf')
        if remaining == 0: return 0
        return 1 + min(dp(remaining - c) for c in coins)
    result = dp(amount)
    return result if result != float('inf') else -1
# State: remaining amount (0 to amount)
# Transitions: try each coin denomination
# Time: O(amount * len(coins)), Space: O(amount)
```


## Longest Common Subsequence (LeetCode 1143)


```
def lcs(s1, s2):
    @lru_cache(maxsize=None)
    def dp(i, j):
        if i == len(s1) or j == len(s2): return 0
        if s1[i] == s2[j]:
            return 1 + dp(i+1, j+1)
        return max(dp(i+1, j), dp(i, j+1))
    return dp(0, 0)
# State: (i, j) = position in s1 and s2
# O(m*n) states, O(1) per state = O(m*n) total
```


## Word Break (LeetCode 139)


```
def word_break(s, wordDict):
    words = set(wordDict)
    @lru_cache(maxsize=None)
    def dp(start):
        if start == len(s): return True
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in words and dp(end):
                return True
        return False
    return dp(0)
# State: start index (0 to n)
# Try all prefixes from start — O(n^2) states * O(n) string check = O(n^3)
```


## Regular Expression Matching (LeetCode 10)


```
def is_match(s, p):
    @lru_cache(maxsize=None)
    def dp(i, j):
        if j == len(p): return i == len(s)
        first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')
        if j + 1 < len(p) and p[j+1] == '*':
            # either skip "x*" entirely, or use it (if first char matches)
            return dp(i, j+2) or (first_match and dp(i+1, j))
        return first_match and dp(i+1, j+1)
    return dp(0, 0)
# State: (i, j) = position in s and p
# O(m*n) states
```


## Edit Distance (LeetCode 72)


```
def min_distance(word1, word2):
    @lru_cache(maxsize=None)
    def dp(i, j):
        if i == 0: return j   # insert all remaining chars of word2
        if j == 0: return i   # delete all remaining chars of word1
        if word1[i-1] == word2[j-1]:
            return dp(i-1, j-1)   # no operation needed
        return 1 + min(
            dp(i-1, j),     # delete from word1
            dp(i, j-1),     # insert into word1
            dp(i-1, j-1)    # replace
        )
    return dp(len(word1), len(word2))
# Classic interview problem: Levenshtein distance
# State: (i, j) = first i chars of word1, first j chars of word2
```


## Decode Ways (LeetCode 91)


```
def num_decodings(s):
    @lru_cache(maxsize=None)
    def dp(i):
        if i == len(s): return 1   # decoded successfully
        if s[i] == '0': return 0   # leading zero — invalid
        result = dp(i + 1)         # single digit
        if i + 1 < len(s) and int(s[i:i+2]) <= 26:
            result += dp(i + 2)    # two digits
        return result
    return dp(0)
```


## Memoization vs. Bottom-Up DP

| Aspect | Memoization (top-down) | Bottom-up DP |
| --- | --- | --- |
| Order | Automatic (lazy) | Manual (must figure out) |
| Only needed states | Yes (sparse problems) | No (fills all states) |
| Stack overflow risk | Yes (deep recursion) | No |
| Space optimization | Hard (cache stores all) | Easy (rolling array) |
| Interview speed | Faster to write | Requires careful indexing |

## Interview Tips

- Use `@lru_cache` in Python — it is production-grade and acceptable in interviews

- Always state the number of distinct states and time per state to derive total complexity

- For 2D memoization (LCS, edit distance, regex matching), the state is (i, j) — a 2D table

- Convert mutable parameters to tuples for lru_cache: `dp(tuple(coins), amount)`

- When interviewers ask "can you do it bottom-up?" — convert by filling the dp array in reverse order of the recursion

- [Uber Interview Guide](https://techinterview.org/uber-software-engineer-interview/)

- [Snap Interview Guide](https://techinterview.org/snap-software-engineer-interview/)

- [Atlassian Interview Guide](https://techinterview.org/atlassian-software-engineer-interview/)

- [LinkedIn Interview Guide](https://techinterview.org/linkedin-software-engineer-interview/)

- [Apple Interview Guide](https://techinterview.org/apple-software-engineer-interview/)

- [Meta Interview Guide](https://techinterview.org/meta-software-engineer-interview/)

Asked at: [Coinbase Interview Guide](https://techinterview.org/coinbase-interview/)