44. Wildcard Matching - Solution

Q: Is Wildcard Matching easy or hard?

Wildcard Matching is classified as a hard problem because it combines string parsing, edge-case handling, and algorithm optimization. Understanding the DP transition rules is manageable, but discovering the linear-time greedy strategy requires deeper insight.

Q: How to solve Wildcard Matching in O(n)?

An O(m+n) solution uses two pointers and a greedy strategy. When a '*' appears in the pattern, store its position and the corresponding string index. If a mismatch happens later, backtrack to the stored star and expand the match by one character. This avoids building a DP table and keeps memory usage constant.

Q: What is the best approach for Wildcard Matching?

The most widely taught solution is Dynamic Programming because it clearly models matching between prefixes of the string and pattern. However, the optimal solution uses a greedy two-pointer technique with backtracking to the last '*' position. That method runs in O(m+n) time and O(1) space, making it more efficient for large inputs.

Q: What data structure is used in Wildcard Matching?

The Dynamic Programming approach uses a 2D boolean DP table to store match states between prefixes of the string and pattern. The greedy solution instead relies on pointer tracking and a few integer variables, avoiding additional data structures entirely.

Q: What is the time complexity of Wildcard Matching?

The Dynamic Programming approach runs in O(m*n) time where m is the length of the string and n is the length of the pattern. The optimized greedy algorithm reduces this to O(m+n) by scanning both strings once while tracking the most recent '*' position.

Q: Wildcard Matching Python or Java solution approach

Both Python and Java implementations usually follow either the DP table method or the greedy two-pointer algorithm. The DP version uses nested loops to fill a boolean matrix, while the greedy version uses pointer indices and star tracking variables to simulate pattern expansion.

Q: Is Wildcard Matching asked at Google, Amazon, or Meta?

Wildcard-style pattern matching problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants test string processing, backtracking, and dynamic programming skills, making this problem a common hard-level interview question.

The problem

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Constraints:

0 <= s.length, p.length <= 2000
s contains only lowercase English letters.
p contains only lowercase English letters, '?' or '*'.

Approach overview

Problem Overview: Wildcard Matching checks whether an entire string s matches a pattern p that may contain two special characters: ? (matches any single character) and * (matches any sequence of characters, including empty). The goal is to return true if the whole string can be matched by the pattern, otherwise false.

Approach 1: Dynamic Programming (O(m*n) time, O(m*n) space)

This approach models the problem as a state transition using dynamic programming. Create a 2D table dp[i][j] where each state represents whether the first i characters of s match the first j characters of p. If characters match or the pattern has ?, the result depends on the previous diagonal state dp[i-1][j-1]. When encountering *, two possibilities exist: treat it as matching zero characters (dp[i][j-1]) or match one more character from the string (dp[i-1][j]). Initialization is critical because leading * characters can match an empty string. This solution systematically evaluates all subproblems and guarantees correctness for every edge case.

DP is reliable for interview discussion because it clearly expresses the recursive relationship between pattern and string prefixes. The tradeoff is memory usage: storing a full table requires O(m*n) space, though it can be optimized to O(n) by keeping only the previous row.

Approach 2: Greedy Two-Pointer Algorithm (O(m+n) time, O(1) space)

A faster solution uses a greedy strategy with two pointers scanning the string and pattern. Track four values: the current index in s, the current index in p, the most recent * position in the pattern, and the position in the string where that star started matching. When characters match or the pattern has ?, advance both pointers. When encountering *, record its position and attempt to match zero characters first. If a mismatch occurs later, backtrack to the last * and expand its match by one additional character in the string.

This works because * can represent any substring length, so the algorithm greedily tries minimal matches and only expands when needed. The scan never moves backward in the pattern except to the stored star position, which keeps the runtime linear. The method relies heavily on careful pointer management and is commonly categorized under string processing techniques.

Recommended for interviews: Interviewers often expect the Dynamic Programming reasoning first because it demonstrates understanding of overlapping subproblems and pattern matching logic. After that, presenting the Greedy two-pointer optimization shows deeper algorithmic insight since it reduces complexity to O(m+n) time and O(1) space. Showing both approaches signals strong problem-solving depth.

Approach 1: Dynamic Programming Approach

The dynamic programming approach uses a 2D table to store results of subproblems. We define dp[i][j] as True if the first i characters in the string s can be matched by the first j characters of the pattern p.

Base Cases:

dp[0][0] is True because an empty pattern matches an empty string.
dp[0][j] is True if p[j-1] is '*', otherwise False.
dp[i][0] is False because a non-empty string cannot be matched by an empty pattern.

Fill the table using the following rules:

If p[j-1] is '*', dp[i][j] is True if dp[i-1][j] or dp[i][j-1] is True.
If p[j-1] is '?' or p[j-1] == s[i-1], dp[i][j] is True if dp[i-1][j-1] is True.

Python

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    for j in range(1, n + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 1]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
            elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]

    return dp[m][n]

Java

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j - 1] && (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1));
                }
            }
        }
        return dp[m][n];
    }
}

C++

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*')
                dp[0][j] = dp[0][j - 1];
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j - 1] && (p[j - 1] == '?' || s[i - 1] == p[j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};

JavaScript

var isMatch = function(s, p) {
    const m = s.length;
    const n = p.length;
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
    dp[0][0] = true;

    for (let j = 1; j <= n; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 1];
        }
    }

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j - 1] === '*') {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            } else if (p[j - 1] === '?' || s[i - 1] === p[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[m][n];
};

#include <stdbool.h>
#include <string.h>

bool isMatch(char * s, char * p) {
    int m = strlen(s);
    int n = strlen(p);
    bool dp[m + 1][n + 1];
    memset(dp, false, sizeof(dp));
    dp[0][0] = true;
    for (int j = 1; j <= n; j++) {
        if (p[j - 1] == '*') dp[0][j] = dp[0][j - 1];
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            } else {
                dp[i][j] = dp[i - 1][j - 1] && (p[j - 1] == '?' || s[i - 1] == p[j - 1]);
            }
        }
    }
    return dp[m][n];
}

public class Solution {
    public bool IsMatch(string s, string p) {
        int m = s.Length;
        int n = p.Length;
        bool[,] dp = new bool[m + 1, n + 1];
        dp[0, 0] = true;

        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                dp[0, j] = dp[0, j - 1];
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '*') {
                    dp[i, j] = dp[i - 1, j] || dp[i, j - 1];
                } else {
                    dp[i, j] = dp[i - 1, j - 1] && (p[j - 1] == '?' || s[i - 1] == p[j - 1]);
                }
            }
        }

        return dp[m, n];
    }
}

This Python implementation also adopts the 2D DP table approach. Here, the dp list-of-lists encapsulates the match possibilities, similar to other languages' implementations.

Complexity

Time Complexity: O(m*n)
Space Complexity: O(m*n)

Try this approach in the editor

Approach 2: Greedy Algorithm Approach

The greedy algorithm approach tracks the position of the last '*' in the pattern and attempts to match remaining characters greedily. We maintain two pointers, one for the string and one for the pattern. When encountering '*', we remember the positions of both pointers in order to backtrack if needed.

If characters in p and s match or if the pattern has '?', both pointers are incremented. For '*', we shift the pattern pointer and remember indices for future potential matches. If there's a mismatch after '*', we use these remembered indices to backtrack.

Python

def isMatch(s: str, p: str) -> bool:
    s_len, p_len = len(s), len(p)
    s_idx = 0
    p_idx = 0
    star_idx = -1
    s_tmp_idx = -1

    while s_idx < s_len:
        if p_idx < p_len and (p[p_idx] == '?' or p[p_idx] == s[s_idx]):
            s_idx += 1
            p_idx += 1
        elif p_idx < p_len and p[p_idx] == '*':
            star_idx = p_idx
            s_tmp_idx = s_idx
            p_idx += 1
        elif star_idx == -1:
            return False
        else:
            p_idx = star_idx + 1
            s_tmp_idx += 1
            s_idx = s_tmp_idx

    while p_idx < p_len and p[p_idx] == '*':
        p_idx += 1

    return p_idx == p_len

Java

public class Solution {
    public boolean isMatch(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        int sIdx = 0, pIdx = 0;
        int starIdx = -1, sTmpIdx = -1;

        while (sIdx < sLen) {
            if (pIdx < pLen && (p.charAt(pIdx) == '?' || p.charAt(pIdx) == s.charAt(sIdx))) {
                sIdx++;
                pIdx++;
            } else if (pIdx < pLen && p.charAt(pIdx) == '*') {
                starIdx = pIdx;
                sTmpIdx = sIdx;
                pIdx++;
            } else if (starIdx == -1) {
                return false;
            } else {
                pIdx = starIdx + 1;
                sTmpIdx++;
                sIdx = sTmpIdx;
            }
        }

        for (int i = pIdx; i < pLen; i++) {
            if (p.charAt(i) != '*') return false;
        }
        return true;
    }
}

C++

#include <string>
using namespace std;

class Solution {
public:
    bool isMatch(string s, string p) {
        int sLen = s.length();
        int pLen = p.length();
        int sIdx = 0, pIdx = 0;
        int starIdx = -1, sTmpIdx = -1;
        
        while (sIdx < sLen) {
            if (pIdx < pLen && (p[pIdx] == '?' || s[sIdx] == p[pIdx])) {
                sIdx++;
                pIdx++;
            } else if (pIdx < pLen && p[pIdx] == '*') {
                starIdx = pIdx;
                sTmpIdx = sIdx;
                pIdx++;
            } else if (starIdx == -1) {
                return false;
            } else {
                pIdx = starIdx + 1;
                sTmpIdx++;
                sIdx = sTmpIdx;
            }
        }
        
        for (int i = pIdx; i < pLen; i++) {
            if (p[i] != '*') return false;
        }
        return true;
    }
};

JavaScript

var isMatch = function(s, p) {
    let sIdx = 0, pIdx = 0, sTmpIdx = -1, starIdx = -1;
    let sLen = s.length, pLen = p.length;

    while (sIdx < sLen) {
        if (pIdx < pLen && (p[pIdx] === '?' || s[sIdx] === p[pIdx])) {
            sIdx++;
            pIdx++;
        } else if (pIdx < pLen && p[pIdx] === '*') {
            starIdx = pIdx;
            sTmpIdx = sIdx;
            pIdx++;
        } else if (starIdx === -1) {
            return false;
        } else {
            pIdx = starIdx + 1;
            sTmpIdx++;
            sIdx = sTmpIdx;
        }
    }

    while (pIdx < pLen && p[pIdx] === '*') {
        pIdx++;
    }

    return pIdx === pLen;
};

#include <stdbool.h>
#include <string.h>

bool isMatch(char *s, char *p) {
    int sLen = strlen(s);
    int pLen = strlen(p);
    int sIdx = 0, pIdx = 0;
    int starIdx = -1, sTmpIdx = -1;

    while (sIdx < sLen) {
        if (pIdx < pLen && (s[sIdx] == p[pIdx] || p[pIdx] == '?')) {
            sIdx++;
            pIdx++;
        } else if (pIdx < pLen && p[pIdx] == '*') {
            starIdx = pIdx;
            sTmpIdx = sIdx;
            pIdx++;
        } else if (starIdx == -1) {
            return false;
        } else {
            pIdx = starIdx + 1;
            sIdx = sTmpIdx + 1;
            sTmpIdx = sIdx;
        }
    }

    for (int i = pIdx; i < pLen; i++) {
        if (p[i] != '*') {
            return false;
        }
    }

    return true;
}

public class Solution {
    public bool IsMatch(string s, string p) {
        int sLen = s.Length;
        int pLen = p.Length;
        int sIdx = 0, pIdx = 0;
        int starIdx = -1, sTmpIdx = -1;

        while (sIdx < sLen) {
            if (pIdx < pLen && (p[pIdx] == '?' || s[sIdx] == p[pIdx])) {
                sIdx++;
                pIdx++;
            } else if (pIdx < pLen && p[pIdx] == '*') {
                starIdx = pIdx;
                sTmpIdx = sIdx;
                pIdx++;
            } else if (starIdx == -1) {
                return false;
            } else {
                pIdx = starIdx + 1;
                sTmpIdx++;
                sIdx = sTmpIdx;
            }
        }

        for (int i = pIdx; i < pLen; i++) {
            if (p[i] != '*') {
                return false;
            }
        }

        return true;
    }
}

The Python implementation effectively replicates the greedy mechanism, seeking to pair current text components with 'p' elements using only essential backtracking when necessary.

Complexity

Time Complexity: O(m + n)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Memoization Search

We design a function dfs(i, j), which represents whether the string s starting from the i-th character matches the string p starting from the j-th character. The answer is dfs(0, 0).

The execution process of the function dfs(i, j) is as follows:

If i geq len(s), then dfs(i, j) is true only when j geq len(p) or p[j] = '*' and dfs(i, j + 1) is true.
If j geq len(p), then dfs(i, j) is false.
If p[j] = '*', then dfs(i, j) is true if and only if dfs(i + 1, j) or dfs(i + 1, j + 1) or dfs(i, j + 1) is true.
Otherwise, dfs(i, j) is true if and only if p[j] = '?' or s[i] = p[j] and dfs(i + 1, j + 1) is true.

To avoid repeated calculations, we use the method of memoization search and store the result of dfs(i, j) in a hash table.

The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the lengths of the strings s and p, respectively.

TypeScript

function isMatch(s: string, p: string): boolean {
    const m = s.length;
    const n = p.length;
    const f: number[][] = Array.from({ length: m + 1 }, () =>
        Array.from({ length: n + 1 }, () => -1),
    );
    const dfs = (i: number, j: number): boolean => {
        if (i >= m) {
            return j >= n || (p[j] === '*' && dfs(i, j + 1));
        }
        if (j >= n) {
            return false;
        }
        if (f[i][j] !== -1) {
            return f[i][j] === 1;
        }
        if (p[j] === '*') {
            f[i][j] = dfs(i + 1, j) || dfs(i, j + 1) ? 1 : 0;
        } else {
            f[i][j] = (p[j] === '?' || s[i] === p[j]) && dfs(i + 1, j + 1) ? 1 : 0;
        }
        return f[i][j] === 1;
    };
    return dfs(0, 0);
}

func isMatch(s string, p string) bool {
	m, n := len(s), len(p)
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	var dfs func(i, j int) bool
	dfs = func(i, j int) bool {
		if i >= m {
			return j >= n || p[j] == '*' && dfs(i, j+1)
		}
		if j >= n {
			return false
		}
		if f[i][j] != 0 {
			return f[i][j] == 1
		}
		f[i][j] = 2
		ok := false
		if p[j] == '*' {
			ok = dfs(i+1, j) || dfs(i+1, j+1) || dfs(i, j+1)
		} else {
			ok = (p[j] == '?' || s[i] == p[j]) && dfs(i+1, j+1)
		}
		if ok {
			f[i][j] = 1
		}
		return ok
	}
	return dfs(0, 0)
}

Try this approach in the editor

Approach 4: Dynamic Programming

We can convert the memoization search in Solution 1 into dynamic programming.

Define f[i][j] to represent whether the first i characters of string s match the first j characters of string p. Initially, f[0][0] = true, indicating that two empty strings are matching. For j \in [1, n], if p[j-1] = '*', then f[0][j] = f[0][j-1].

Next, we consider the case of i \in [1, m] and j \in [1, n]:

If p[j-1] = '*', then f[i][j] = f[i-1][j] \lor f[i][j-1] \lor f[i-1][j-1].
Otherwise, f[i][j] = (p[j-1] = '?' \lor s[i-1] = p[j-1]) \land f[i-1][j-1].

The final answer is f[m][n].

The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the lengths of the strings s and p, respectively.

TypeScript

function isMatch(s: string, p: string): boolean {
    const m: number = s.length;
    const n: number = p.length;
    const f: boolean[][] = Array.from({ length: m + 1 }, () =>
        Array.from({ length: n + 1 }, () => false),
    );
    f[0][0] = true;
    for (let j = 1; j <= n; ++j) {
        if (p.charAt(j - 1) === '*') {
            f[0][j] = f[0][j - 1];
        }
    }
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (p[j - 1] === '*') {
                f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i - 1][j - 1];
            } else {
                f[i][j] = f[i - 1][j - 1] && (p[j - 1] === '?' || s[i - 1] === p[j - 1]);
            }
        }
    }
    return f[m][n];
}

func isMatch(s string, p string) bool {
	m, n := len(s), len(p)
	f := make([][]bool, m+1)
	for i := range f {
		f[i] = make([]bool, n+1)
	}
	f[0][0] = true
	for j := 1; j <= n; j++ {
		if p[j-1] == '*' {
			f[0][j] = f[0][j-1]
		}
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if p[j-1] == '*' {
				f[i][j] = f[i-1][j] || f[i][j-1] || f[i-1][j-1]
			} else {
				f[i][j] = f[i-1][j-1] && (p[j-1] == '?' || s[i-1] == p[j-1])
			}
		}
	}
	return f[m][n]
}

PHP

class Solution {
    /**
     * @param string $s
     * @param string $p
     * @return boolean
     */

    function isMatch($s, $p) {
        $lengthS = strlen($s);
        $lengthP = strlen($p);
        $dp = [];
        for ($i = 0; $i <= $lengthS; $i++) {
            $dp[$i] = array_fill(0, $lengthP + 1, false);
        }
        $dp[0][0] = true;

        for ($i = 1; $i <= $lengthP; $i++) {
            if ($p[$i - 1] == '*') {
                $dp[0][$i] = $dp[0][$i - 1];
            }
        }
        for ($i = 1; $i <= $lengthS; $i++) {
            for ($j = 1; $j <= $lengthP; $j++) {
                if ($p[$j - 1] == '?' || $s[$i - 1] == $p[$j - 1]) {
                    $dp[$i][$j] = $dp[$i - 1][$j - 1];
                } elseif ($p[$j - 1] == '*') {
                    $dp[$i][$j] = $dp[$i][$j - 1] || $dp[$i - 1][$j];
                }
            }
        }
        return $dp[$lengthS][$lengthP];
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Approach	Time Complexity: *O(mn) Space Complexity: O(mn)*
Greedy Algorithm Approach	Time Complexity: O(m + n) Space Complexity: O(1)
Memoization Search	–
Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming	O(m*n)	O(m*n) or O(n)	General case when you want a clear, systematic solution that handles all edge cases
Greedy Two-Pointer	O(m+n)	O(1)	Optimal solution when performance matters and pattern contains many '*' wildcards

Frequently asked questions

Is Wildcard Matching easy or hard?

Wildcard Matching is classified as a hard problem because it combines string parsing, edge-case handling, and algorithm optimization. Understanding the DP transition rules is manageable, but discovering the linear-time greedy strategy requires deeper insight.

How to solve Wildcard Matching in O(n)?

An O(m+n) solution uses two pointers and a greedy strategy. When a '*' appears in the pattern, store its position and the corresponding string index. If a mismatch happens later, backtrack to the stored star and expand the match by one character. This avoids building a DP table and keeps memory usage constant.

What is the best approach for Wildcard Matching?

The most widely taught solution is Dynamic Programming because it clearly models matching between prefixes of the string and pattern. However, the optimal solution uses a greedy two-pointer technique with backtracking to the last '*' position. That method runs in O(m+n) time and O(1) space, making it more efficient for large inputs.

What data structure is used in Wildcard Matching?

The Dynamic Programming approach uses a 2D boolean DP table to store match states between prefixes of the string and pattern. The greedy solution instead relies on pointer tracking and a few integer variables, avoiding additional data structures entirely.

What is the time complexity of Wildcard Matching?

The Dynamic Programming approach runs in O(m*n) time where m is the length of the string and n is the length of the pattern. The optimized greedy algorithm reduces this to O(m+n) by scanning both strings once while tracking the most recent '*' position.

Wildcard Matching Python or Java solution approach

Both Python and Java implementations usually follow either the DP table method or the greedy two-pointer algorithm. The DP version uses nested loops to fill a boolean matrix, while the greedy version uses pointer indices and star tracking variables to simulate pattern expansion.

Is Wildcard Matching asked at Google, Amazon, or Meta?

Wildcard-style pattern matching problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants test string processing, backtracking, and dynamic programming skills, making this problem a common hard-level interview question.

Wildcard Matching solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Greedy Algorithm Approach

Approach 3: Memoization Search

Approach 4: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Wildcard Matching solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Greedy Algorithm Approach

Approach 3: Memoization Search

Approach 4: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems