Regular Expression Matching solution and explanation
Google
Infosys
9 more videos on this problem
Regular Expression Matching - Dynamic Programming Top-Down Memoization - Leetcode 10NeetCode · 27:56 · 242K views
Regular Expression Matching | Brute Force | Optimal | Recursion Concepts And QuestionscodestorywithMIK · 54:24 · 27K views
Regular Expression Matching -- Leetcode #10elidrinkscoffee · 13:38 · 7K views
Leetcode 10 Regular Expression Matching (Java) - Beats 100%TheAnalyticGuy · 12:40 · 6K views
Regular Expression Matching Python Solution - LeetCode #10Professor Oakes · 7:57 · 5K views
Regular Expression Matching | LeetCode 10 DPDestination FAANG · 27:56 · 3K views
Leetcode 10. Regular Expression Matching Explanation + Coding (Java) #LeetCode #Java #InterviewAlgorithms Simplified · 30:15 · 1K views
10. Regular Expression Matching (Leetcode Hard)Programming Live with Larry · 27:14 · 975 views
Regular Expression Matching - LeetCode #10 - C++Sean Chuah · 12:28 · 690 views
Regular Expression Dynamic ProgrammingTushar Roy - Coding Made Simple · 18:34 · 274K views
The problem
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
'.'Matches any single character.'*'Matches zero or more of the preceding element.
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 = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input: s = "ab", p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)".
Constraints:
1 <= s.length <= 201 <= p.length <= 20scontains only lowercase English letters.pcontains only lowercase English letters,'.', and'*'.- It is guaranteed for each appearance of the character
'*', there will be a previous valid character to match.
Approach overview
Problem Overview: Given a string s and a pattern p, determine if the entire string matches the pattern. The pattern supports two special characters: . which matches any single character, and * which means zero or more occurrences of the preceding element.
Approach 1: Recursive Approach with Memoization (Time: O(m*n), Space: O(m*n))
This method models the problem exactly how the pattern matching works conceptually. Start from indices i in the string and j in the pattern and recursively check if the remaining substrings match. When encountering *, two choices exist: skip the pattern segment (x*) or consume one matching character and stay on the same pattern index. Memoization stores results for states (i, j) to avoid recomputing overlapping subproblems. Without caching the recursion would explode exponentially, but memoization reduces it to O(m*n) since each state is computed once.
This approach is intuitive because it directly mirrors the matching rules of regular expressions. It is a strong choice when you want clear logic and quick implementation during interviews. The recursion depth is at most O(m + n), and the memo table ensures previously solved states are reused.
Approach 2: Dynamic Programming Tabulation (Time: O(m*n), Space: O(m*n))
The tabulation approach builds a bottom‑up DP table where dp[i][j] represents whether the first i characters of the string match the first j characters of the pattern. The transition depends on the current pattern character. If characters match directly or through ., inherit the result from dp[i-1][j-1]. If the pattern contains *, handle two cases: treat x* as zero occurrences (dp[i][j-2]) or consume one matching character if s[i-1] matches the preceding pattern character (dp[i-1][j]).
The DP table is filled row by row, carefully initializing cases where patterns like a*, a*b*, or similar can match an empty string. This approach removes recursion entirely and guarantees predictable performance with O(m*n) time and space complexity. It is often easier to debug because every subproblem is visible in the table.
Both approaches rely on breaking the problem into smaller matching states. They heavily use concepts from String processing and Dynamic Programming, while the first approach also demonstrates recursive state exploration from Recursion.
Recommended for interviews: Interviewers typically expect the dynamic programming formulation because it clearly demonstrates understanding of state transitions and overlapping subproblems. Starting with the recursive reasoning and then adding memoization shows strong problem‑solving skills, while presenting the tabulation DP proves you can convert recursive thinking into an efficient iterative solution.
Approach 1: Recursive Approach with Memoization
This approach uses recursion with memoization to solve the problem efficiently. We recursively compare characters of the input string and the pattern, addressing special characters like '.' and '*'. The memoization is used to store results of sub-problems to avoid redundant calculations, which drastically improves the performance.
def isMatch(s, p):
memo = {}
def dfs(i, j):
if (i, j) in memo:
return memo[(i, j)]
if j == len(p):
return i == len(s)
match = i < len(s) and (s[i] == p[j] or p[j] == '.')
if (j + 1) < len(p) and p[j+1] == '*':
memo[(i, j)] = dfs(i, j + 2) or (match and dfs(i + 1, j))
return memo[(i, j)]
if match:
memo[(i, j)] = dfs(i + 1, j + 1)
return memo[(i, j)]
memo[(i, j)] = False
return False
return dfs(0, 0)public class Solution {
public boolean isMatch(String s, String p) {
Boolean[][] memo = new Boolean[s.length() + 1][p.length() + 1];
return dfs(0, 0, s, p, memo);
}
private boolean dfs(int i, int j, String s, String p, Boolean[][] memo) {
if (memo[i][j] != null) {
return memo[i][j];
}
if (j == p.length()) {
return i == s.length();
}
boolean match = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
memo[i][j] = dfs(i, j + 2, s, p, memo) || (match && dfs(i + 1, j, s, p, memo));
return memo[i][j];
}
if (match) {
memo[i][j] = dfs(i + 1, j + 1, s, p, memo);
return memo[i][j];
}
memo[i][j] = false;
return false;
}
}#include <vector>
#include <string>
using namespace std;
class Solution {
public:
bool isMatch(string s, string p) {
vector<vector<int>> memo(s.size() + 1, vector<int>(p.size() + 1, -1));
return dfs(0, 0, s, p, memo);
}
bool dfs(int i, int j, const string& s, const string& p, vector<vector<int>>& memo) {
if (memo[i][j] != -1) {
return memo[i][j];
}
if (j == p.size()) {
return i == s.size();
}
bool match = i < s.size() && (s[i] == p[j] || p[j] == '.');
if (j + 1 < p.size() && p[j + 1] == '*') {
memo[i][j] = dfs(i, j + 2, s, p, memo) || (match && dfs(i + 1, j, s, p, memo));
return memo[i][j];
}
if (match) {
memo[i][j] = dfs(i + 1, j + 1, s, p, memo);
return memo[i][j];
}
memo[i][j] = false;
return false;
}
};function isMatch(s, p) {
const memo = Array.from({ length: s.length + 1 }, () => Array(p.length + 1).fill(undefined));
function dfs(i, j) {
if (memo[i][j] !== undefined) {
return memo[i][j];
}
if (j === p.length) {
return i === s.length;
}
const match = i < s.length && (s[i] === p[j] || p[j] === '.');
if ((j + 1) < p.length && p[j + 1] === '*') {
memo[i][j] = dfs(i, j + 2) || (match && dfs(i + 1, j));
return memo[i][j];
}
if (match) {
memo[i][j] = dfs(i + 1, j + 1);
return memo[i][j];
}
memo[i][j] = false;
return false;
}
return dfs(0, 0);
}#include <stdbool.h>
#include <string.h>
bool dfs(int i, int j, const char* s, const char* p, int* memo, int slen, int plen) {
if (memo[i * (plen + 1) + j] != -1) {
return memo[i * (plen + 1) + j];
}
if (j == plen) {
return i == slen;
}
bool match = i < slen && (s[i] == p[j] || p[j] == '.');
if ((j + 1) < plen && p[j + 1] == '*') {
memo[i * (plen + 1) + j] = dfs(i, j + 2, s, p, memo, slen, plen) || (match && dfs(i + 1, j, s, p, memo, slen, plen));
return memo[i * (plen + 1) + j];
}
if (match) {
memo[i * (plen + 1) + j] = dfs(i + 1, j + 1, s, p, memo, slen, plen);
return memo[i * (plen + 1) + j];
}
memo[i * (plen + 1) + j] = false;
return false;
}
bool isMatch(const char* s, const char* p) {
int slen = strlen(s);
int plen = strlen(p);
int* memo = (int*)malloc((slen + 1) * (plen + 1) * sizeof(int));
for (int i = 0; i <= slen; ++i) {
for (int j = 0; j <= plen; ++j) {
memo[i * (plen + 1) + j] = -1;
}
}
bool result = dfs(0, 0, s, p, memo, slen, plen);
free(memo);
return result;
}using System;
public class Solution {
public bool IsMatch(string s, string p) {
int sLen = s.Length, pLen = p.Length;
bool?[,] memo = new bool?[sLen + 1, pLen + 1];
return dfs(0, 0, s, p, memo);
}
private bool dfs(int i, int j, string s, string p, bool?[,] memo) {
if (memo[i, j] != null) {
return memo[i, j].Value;
}
if (j == p.Length) {
return i == s.Length;
}
bool match = i < s.Length && (s[i] == p[j] || p[j] == '.');
if (j + 1 < p.Length && p[j + 1] == '*') {
memo[i, j] = dfs(i, j + 2, s, p, memo) || (match && dfs(i + 1, j, s, p, memo));
return memo[i, j].Value;
}
if (match) {
memo[i, j] = dfs(i + 1, j + 1, s, p, memo);
return memo[i, j].Value;
}
memo[i, j] = false;
return false;
}
}The Python solution uses a depth-first search (DFS) approach with memoization to tackle overlapping subproblems. We check if characters at position i in the string and j in the pattern match directly or through special symbols. The '*' in the pattern is handled by either skipping it or considering it as multiple matches.
Time Complexity: O(m * n), where m and n are the lengths of the string and pattern, respectively. We solve every subproblem once and store the result.
Space Complexity: O(m * n) due to recursion stack and memoization storage.
Approach 2: Dynamic Programming Tabulation
This approach involves using a DP table to solve the problem by filling up a boolean matrix iteratively. This avoids recursion and stacks overhead, improving performance in certain scenarios. Each cell in the table represents whether the substring of the pattern matches the substring of the input.
def isMatch(s, p):
dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
dp[0][0] = True
for j in range(1, len(p)):
if p[j] == '*':
dp[0][j + 1] = dp[0][j - 1]
for i in range(len(s)):
for j in range(len(p)):
if p[j] == '.' or s[i] == p[j]:
dp[i + 1][j + 1] = dp[i][j]
elif p[j] == '*':
dp[i + 1][j + 1] = dp[i + 1][j - 1] or (dp[i][j + 1] if p[j-1] == s[i] or p[j-1] == '.' else False)
return dp[-1][-1]public class Solution {
public boolean isMatch(String s, String p) {
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true;
for (int j = 1; j < p.length(); j++) {
if (p.charAt(j) == '*') {
dp[0][j + 1] = dp[0][j - 1];
}
}
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) == '.' || p.charAt(j) == s.charAt(i)) {
dp[i + 1][j + 1] = dp[i][j];
} else if (p.charAt(j) == '*') {
dp[i + 1][j + 1] = dp[i + 1][j - 1] || (dp[i][j + 1] && (p.charAt(j - 1) == s.charAt(i) || p.charAt(j - 1) == '.'));
}
}
}
return dp[s.length()][p.length()];
}
}#include <vector>
#include <string>
using namespace std;
class Solution {
public:
bool isMatch(string s, string p) {
vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));
dp[0][0] = true;
for (int j = 1; j < p.size(); ++j) {
if (p[j] == '*') {
dp[0][j + 1] = dp[0][j - 1];
}
}
for (int i = 0; i < s.size(); ++i) {
for (int j = 0; j < p.size(); ++j) {
if (p[j] == '.' || s[i] == p[j]) {
dp[i + 1][j + 1] = dp[i][j];
} else if (p[j] == '*') {
dp[i + 1][j + 1] = dp[i + 1][j - 1] || (dp[i][j + 1] && (s[i] == p[j - 1] || p[j - 1] == '.'));
}
}
}
return dp[s.size()][p.size()];
}
};function isMatch(s, p) {
const dp = Array.from({ length: s.length + 1 }, () => Array(p.length + 1).fill(false));
dp[0][0] = true;
for (let j = 1; j < p.length; j++) {
if (p[j] === '*') {
dp[0][j + 1] = dp[0][j - 1];
}
}
for (let i = 0; i < s.length; i++) {
for (let j = 0; j < p.length; j++) {
if (p[j] === '.' || s[i] === p[j]) {
dp[i + 1][j + 1] = dp[i][j];
} else if (p[j] === '*') {
dp[i + 1][j + 1] = dp[i + 1][j - 1] || (dp[i][j + 1] && (p[j - 1] === s[i] || p[j - 1] === '.'));
}
}
}
return dp[s.length][p.length];
}#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
bool isMatch(const char* s, const char* p) {
int slen = strlen(s), plen = strlen(p);
bool** dp = (bool**)malloc((slen + 1) * sizeof(bool*));
for (int i = 0; i <= slen; ++i) {
dp[i] = (bool*)malloc((plen + 1) * sizeof(bool));
}
dp[0][0] = true;
for (int j = 1; j < plen; ++j) {
if (p[j] == '*') {
dp[0][j + 1] = dp[0][j - 1];
}
}
for (int i = 0; i < slen; ++i) {
for (int j = 0; j < plen; ++j) {
if (p[j] == '.' || p[j] == s[i]) {
dp[i + 1][j + 1] = dp[i][j];
} else if (p[j] == '*') {
dp[i + 1][j + 1] = dp[i + 1][j - 1] || (dp[i][j + 1] && (p[j - 1] == s[i] || p[j - 1] == '.'));
} else {
dp[i + 1][j + 1] = false;
}
}
}
bool result = dp[slen][plen];
for (int i = 0; i <= slen; ++i) {
free(dp[i]);
}
free(dp);
return result;
}public class Solution {
public bool IsMatch(string s, string p) {
var dp = new bool[s.Length + 1, p.Length + 1];
dp[0, 0] = true;
for (int j = 1; j < p.Length; j++) {
if (p[j] == '*') {
dp[0, j + 1] = dp[0, j - 1];
}
}
for (int i = 0; i < s.Length; i++) {
for (int j = 0; j < p.Length; j++) {
if (p[j] == '.' || s[i] == p[j]) {
dp[i + 1, j + 1] = dp[i, j];
} else if (p[j] == '*') {
dp[i + 1, j + 1] = dp[i + 1, j - 1] || (dp[i, j + 1] && (p[j - 1] == s[i] || p[j - 1] == '.'));
}
}
}
return dp[s.Length, p.Length];
}
}The Python DP solution constructs a 2D boolean array where dp[i][j] signifies if the first i characters of the string match the first j characters of the pattern. The matrix is initialized with the base conditions and filled based on the characters in pattern string, iteratively updating for mismatches dictated by '*' or '.'.
Time Complexity: O(m * n) since we traverse the complete matrix.
Space Complexity: O(m * n) due to the DP table used to store subproblem solutions.
Approach 3: Memoization Search
We design a function dfs(i, j), which indicates whether the i-th character of s matches the j-th character of p. The answer is dfs(0, 0).
The calculation process of the function dfs(i, j) is as follows:
- If
jhas reached the end ofp, then ifihas also reached the end ofs, the match is successful, otherwise, the match fails. - If the next character of
jis'*', we can choose to match0s[i]characters, which isdfs(i, j + 2). Ifi \lt mands[i]matchesp[j], we can choose to match1s[i]character, which isdfs(i + 1, j). - If the next character of
jis not'*', then ifi \lt mands[i]matchesp[j], it isdfs(i + 1, j + 1). Otherwise, the match fails.
During the process, we can use memoization search to avoid repeated calculations.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the lengths of s and p respectively.
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 j >= n {
return i == m
}
if f[i][j] != 0 {
return f[i][j] == 1
}
res := -1
if j+1 < n && p[j+1] == '*' {
if dfs(i, j+2) || (i < m && (s[i] == p[j] || p[j] == '.') && dfs(i+1, j)) {
res = 1
}
} else if i < m && (s[i] == p[j] || p[j] == '.') && dfs(i+1, j+1) {
res = 1
}
f[i][j] = res
return res == 1
}
return dfs(0, 0)
}impl Solution {
pub fn is_match(s: String, p: String) -> bool {
let (m, n) = (s.len(), p.len());
let mut f = vec![vec![0; n + 1]; m + 1];
fn dfs(
s: &Vec<char>,
p: &Vec<char>,
f: &mut Vec<Vec<i32>>,
i: usize,
j: usize,
m: usize,
n: usize,
) -> bool {
if j >= n {
return i == m;
}
if f[i][j] != 0 {
return f[i][j] == 1;
}
let mut res = -1;
if j + 1 < n && p[j + 1] == '*' {
if dfs(s, p, f, i, j + 2, m, n)
|| (i < m && (s[i] == p[j] || p[j] == '.') && dfs(s, p, f, i + 1, j, m, n))
{
res = 1;
}
} else if i < m && (s[i] == p[j] || p[j] == '.') && dfs(s, p, f, i + 1, j + 1, m, n) {
res = 1;
}
f[i][j] = res;
res == 1
}
dfs(
&s.chars().collect(),
&p.chars().collect(),
&mut f,
0,
0,
m,
n,
)
}
}class Solution {
/**
* @param String $s
* @param String $p
* @return Boolean
*/
function isMatch($s, $p) {
$m = strlen($s);
$n = strlen($p);
$f = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
$dfs = function ($i, $j) use (&$s, &$p, $m, $n, &$f, &$dfs) {
if ($j >= $n) {
return $i == $m;
}
if ($f[$i][$j] != 0) {
return $f[$i][$j] == 1;
}
$res = -1;
if ($j + 1 < $n && $p[$j + 1] == '*') {
if (
$dfs($i, $j + 2) ||
($i < $m && ($s[$i] == $p[$j] || $p[$j] == '.') && $dfs($i + 1, $j))
) {
$res = 1;
}
} elseif ($i < $m && ($s[$i] == $p[$j] || $p[$j] == '.') && $dfs($i + 1, $j + 1)) {
$res = 1;
}
$f[$i][$j] = $res;
return $res == 1;
};
return $dfs(0, 0);
}
}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. The answer is f[m][n]. Initialize f[0][0] = true, indicating that the empty string and the empty regular expression match.
Similar to Solution 1, we can discuss different cases.
- If
p[j - 1]is'*', we can choose to match0s[i - 1]characters, which isf[i][j] = f[i][j - 2]. Ifs[i - 1]matchesp[j - 2], we can choose to match1s[i - 1]character, which isf[i][j] = f[i][j] \lor f[i - 1][j]. - If
p[j - 1]is not'*', then ifs[i - 1]matchesp[j - 1], it isf[i][j] = f[i - 1][j - 1]. Otherwise, the match fails.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the lengths of s and p respectively.
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 i := 0; i <= m; i++ {
for j := 1; j <= n; j++ {
if p[j-1] == '*' {
f[i][j] = f[i][j-2]
if i > 0 && (p[j-2] == '.' || p[j-2] == s[i-1]) {
f[i][j] = f[i][j] || f[i-1][j]
}
} else if i > 0 && (p[j-1] == '.' || p[j-1] == s[i-1]) {
f[i][j] = f[i-1][j-1]
}
}
}
return f[m][n]
}impl Solution {
pub fn is_match(s: String, p: String) -> bool {
let m = s.len();
let n = p.len();
let mut f = vec![vec![false; n + 1]; m + 1];
f[0][0] = true;
let s: Vec<char> = s.chars().collect();
let p: Vec<char> = p.chars().collect();
for i in 0..=m {
for j in 1..=n {
if p[j - 1] == '*' {
f[i][j] = f[i][j - 2];
if i > 0 && (p[j - 2] == '.' || p[j - 2] == s[i - 1]) {
f[i][j] = f[i][j] || f[i - 1][j];
}
} else if i > 0 && (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
f[i][j] = f[i - 1][j - 1];
}
}
}
f[m][n]
}
}class Solution {
/**
* @param String $s
* @param String $p
* @return Boolean
*/
function isMatch($s, $p) {
$m = strlen($s);
$n = strlen($p);
$f = array_fill(0, $m + 1, array_fill(0, $n + 1, false));
$f[0][0] = true;
for ($i = 0; $i <= $m; $i++) {
for ($j = 1; $j <= $n; $j++) {
if ($p[$j - 1] == '*') {
$f[$i][$j] = $f[$i][$j - 2];
if ($i > 0 && ($p[$j - 2] == '.' || $p[$j - 2] == $s[$i - 1])) {
$f[$i][$j] = $f[$i][$j] || $f[$i - 1][$j];
}
} elseif ($i > 0 && ($p[$j - 1] == '.' || $p[$j - 1] == $s[$i - 1])) {
$f[$i][$j] = $f[$i - 1][$j - 1];
}
}
}
return $f[$m][$n];
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Approach with Memoization | Time Complexity: O(m * n), where m and n are the lengths of the string and pattern, respectively. We solve every subproblem once and store the result. |
| Dynamic Programming Tabulation | Time Complexity: O(m * n) since we traverse the complete matrix. |
| Memoization Search | – |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(m*n) | O(m*n) | When explaining the problem recursively or deriving the DP state from first principles |
| Dynamic Programming Tabulation | O(m*n) | O(m*n) | Preferred in interviews for deterministic performance and clear state transitions |
Frequently asked questions
Is Regular Expression Matching easy or hard?
Regular Expression Matching is classified as a Hard problem because handling the '*' operator introduces branching decisions and overlapping subproblems. A correct solution requires careful dynamic programming state design and precise handling of pattern edge cases.
Regular Expression Matching Python/Java solution
Python and Java implementations typically use either memoized recursion with a dictionary or a 2D DP array. Both follow the same transitions: direct character match or '.', and special handling for '*' that allows skipping the preceding element or consuming characters repeatedly.
How to solve Regular Expression Matching in O(n)?
Regular Expression Matching cannot generally be solved in O(n) time because the pattern may contain '*' operators that create multiple matching possibilities. The standard optimal approach evaluates all combinations of string and pattern prefixes, resulting in O(m*n) complexity using dynamic programming.
What is the best approach for Regular Expression Matching?
Dynamic programming is the most reliable approach. Both memoized recursion and bottom-up tabulation evaluate states (i, j) representing prefixes of the string and pattern, leading to O(m*n) time complexity. The tabulation version is often preferred in interviews because it clearly shows state transitions and avoids recursion overhead.
Is Regular Expression Matching asked at Google/Amazon/Meta?
Regular Expression Matching is a well-known hard interview problem frequently discussed in preparation resources for companies like Google, Amazon, and Meta. It tests dynamic programming design, recursion with memoization, and careful handling of edge cases involving pattern operators.
What data structure is used in Regular Expression Matching?
The main structure is a 2D dynamic programming table or memoization cache keyed by indices (i, j). Each entry stores whether a prefix of the string matches a prefix of the pattern. This structure efficiently avoids recomputation of overlapping subproblems.
What is the time complexity of Regular Expression Matching?
The optimal solution runs in O(m*n) time where m is the length of the input string and n is the length of the pattern. Each state (i, j) representing a substring and subpattern pair is computed once. Space complexity is also O(m*n) for storing memoization or the DP table.