Regular Expression Matching
Regular Expression Matching is a hard dynamic programming problem solved with the strings pattern.
The best approach, optimal (bottom-up dp table), runs in O(m · n) time and O(m · n) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (plain recursion) up.
Problem
You are given a text s and a pattern p. The pattern uses two special symbols:
.stands for any single character.*means “zero or more copies of the element right before it”.
Return true if the pattern matches the entire text, not just a part of it, and false otherwise.
Examples
Example 1
- Input
s = "abbbc", p = "ab*c"- Output
true- Why
b*absorbs the three b's, and the a and c match themselves.
Example 2
- Input
s = "xy", p = ".*z"- Output
false- Why
.*can cover "xy", but the pattern still needs a final z that the text does not have.
Example 3
- Input
s = "fee", p = "f.*e*"- Output
true- Why
.*matches "ee" ande*matches nothing (or.*matches "e" ande*the last e).
Constraints
1 <= s.length <= 201 <= p.length <= 20shas only lowercase English letters.phas only lowercase English letters,.and*.- Every
*follows a letter or a.(never at the start, never two in a row).
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 17 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (plain recursion) | O(2^(m + n)) in the worst case | O(m + n) |
| Better (recursion with memoization) | O(m · n) | O(m · n) |
| Optimal (bottom-up DP table) | O(m · n) | O(m · n) |
1Brute force (plain recursion)
O(2^(m + n)) in the worst caseEvery star doubles the choices, and the same (i, j) pair is solved again and again.O(m + n)Recursion depth is at most m + n.Define match(i, j) as whether s[i..] matches p[j..]. If the next pattern element is starred, either skip it (match(i, j + 2)) or, when the current characters agree, eat one text character and keep the star (match(i + 1, j)). Otherwise the characters must agree and both indices move forward.
- If j == p.length, return i == s.length.
- first = i < s.length and (p[j] == s[i] or p[j] == '.').
- If p[j + 1] == '*': return match(i, j + 2) or (first and match(i + 1, j)).
- Else return first and match(i + 1, j + 1).
class Solution {
public boolean isMatch(String s, String p) {
return match(s, p, 0, 0);
}
private boolean match(String s, String p, int i, int j) {
if (j == p.length()) {
return i == s.length();
}
boolean first = i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
return match(s, p, i, j + 2) || (first && match(s, p, i + 1, j));
}
return first && match(s, p, i + 1, j + 1);
}
}class Solution:
def isMatch(self, s: str, p: str) -> bool:
def match(i: int, j: int) -> bool:
if j == len(p):
return i == len(s)
first = i < len(s) and (p[j] == s[i] or p[j] == '.')
if j + 1 < len(p) and p[j + 1] == '*':
return match(i, j + 2) or (first and match(i + 1, j))
return first and match(i + 1, j + 1)
return match(0, 0)class Solution {
public:
bool isMatch(string s, string p) {
return match(s, p, 0, 0);
}
private:
bool match(const string& s, const string& p, int i, int j) {
if (j == (int)p.size()) {
return i == (int)s.size();
}
bool first = i < (int)s.size() && (p[j] == s[i] || p[j] == '.');
if (j + 1 < (int)p.size() && p[j + 1] == '*') {
return match(s, p, i, j + 2) || (first && match(s, p, i + 1, j));
}
return first && match(s, p, i + 1, j + 1);
}
};function isMatch(s, p) {
const match = (i, j) => {
if (j === p.length) {
return i === s.length;
}
const first = i < s.length && (p[j] === s[i] || p[j] === '.');
if (j + 1 < p.length && p[j + 1] === '*') {
return match(i, j + 2) || (first && match(i + 1, j));
}
return first && match(i + 1, j + 1);
};
return match(0, 0);
}2Better (recursion with memoization)
O(m · n)(m + 1)(n + 1) states, each doing O(1) work besides its recursive calls.O(m · n)The memo table plus a recursion stack of depth up to m + n.The same recursion, but remember the answer for each (i, j) pair the first time it is computed. Each pair is then solved once.
- Create a memo table of size (m + 1) x (n + 1), initially unknown.
- In match(i, j), return the stored value if present.
- Otherwise compute it with the same rules as the plain recursion and store it.
class Solution {
private Boolean[][] memo;
public boolean isMatch(String s, String p) {
memo = new Boolean[s.length() + 1][p.length() + 1];
return match(s, p, 0, 0);
}
private boolean match(String s, String p, int i, int j) {
if (memo[i][j] != null) {
return memo[i][j];
}
boolean ans;
if (j == p.length()) {
ans = i == s.length();
} else {
boolean first = i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
ans = match(s, p, i, j + 2) || (first && match(s, p, i + 1, j));
} else {
ans = first && match(s, p, i + 1, j + 1);
}
}
memo[i][j] = ans;
return ans;
}
}class Solution:
def isMatch(self, s: str, p: str) -> bool:
memo = {}
def match(i: int, j: int) -> bool:
if (i, j) in memo:
return memo[(i, j)]
if j == len(p):
ans = i == len(s)
else:
first = i < len(s) and (p[j] == s[i] or p[j] == '.')
if j + 1 < len(p) and p[j + 1] == '*':
ans = match(i, j + 2) or (first and match(i + 1, j))
else:
ans = first and match(i + 1, j + 1)
memo[(i, j)] = ans
return ans
return match(0, 0)class Solution {
public:
bool isMatch(string s, string p) {
memo.assign(s.size() + 1, vector<int>(p.size() + 1, -1));
return match(s, p, 0, 0);
}
private:
vector<vector<int>> memo;
bool match(const string& s, const string& p, int i, int j) {
if (memo[i][j] != -1) {
return memo[i][j];
}
bool ans;
if (j == (int)p.size()) {
ans = i == (int)s.size();
} else {
bool first = i < (int)s.size() && (p[j] == s[i] || p[j] == '.');
if (j + 1 < (int)p.size() && p[j + 1] == '*') {
ans = match(s, p, i, j + 2) || (first && match(s, p, i + 1, j));
} else {
ans = first && match(s, p, i + 1, j + 1);
}
}
memo[i][j] = ans;
return ans;
}
};function isMatch(s, p) {
const memo = Array.from({ length: s.length + 1 }, () => new Array(p.length + 1).fill(null));
const match = (i, j) => {
if (memo[i][j] !== null) {
return memo[i][j];
}
let ans;
if (j === p.length) {
ans = i === s.length;
} else {
const first = i < s.length && (p[j] === s[i] || p[j] === '.');
if (j + 1 < p.length && p[j + 1] === '*') {
ans = match(i, j + 2) || (first && match(i + 1, j));
} else {
ans = first && match(i + 1, j + 1);
}
}
memo[i][j] = ans;
return ans;
};
return match(0, 0);
}3Optimal (bottom-up DP table)
O(m · n)Each of the (m + 1)(n + 1) cells is filled once in O(1).O(m · n)The full table; no recursion stack.Fill dp[i][j] = whether s[i..] matches p[j..], starting from the ends of both strings. The empty pattern matches only the empty text, and every other cell uses the same two rules as the recursion, reading cells that are already filled.
- dp[m][n] = true; the rest of row n (pattern used up, text left) stays false.
- For i from m down to 0, for j from n - 1 down to 0:
- first = i < m and (p[j] == s[i] or p[j] == '.').
- If j + 1 < n and p[j + 1] == '*': dp[i][j] = dp[i][j + 2] or (first and dp[i + 1][j]).
- Else dp[i][j] = first and dp[i + 1][j + 1].
- Return dp[0][0].
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[m][n] = true;
for (int i = m; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
boolean first = i < m && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
if (j + 1 < n && p.charAt(j + 1) == '*') {
dp[i][j] = dp[i][j + 2] || (first && dp[i + 1][j]);
} else {
dp[i][j] = first && dp[i + 1][j + 1];
}
}
}
return dp[0][0];
}
}class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[m][n] = True
for i in range(m, -1, -1):
for j in range(n - 1, -1, -1):
first = i < m and (p[j] == s[i] or p[j] == '.')
if j + 1 < n and p[j + 1] == '*':
dp[i][j] = dp[i][j + 2] or (first and dp[i + 1][j])
else:
dp[i][j] = first and dp[i + 1][j + 1]
return dp[0][0]class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[m][n] = true;
for (int i = m; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
bool first = i < m && (p[j] == s[i] || p[j] == '.');
if (j + 1 < n && p[j + 1] == '*') {
dp[i][j] = dp[i][j + 2] || (first && dp[i + 1][j]);
} else {
dp[i][j] = first && dp[i + 1][j + 1];
}
}
}
return dp[0][0];
}
};function isMatch(s, p) {
const m = s.length, n = p.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
dp[m][n] = true;
for (let i = m; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
const first = i < m && (p[j] === s[i] || p[j] === '.');
if (j + 1 < n && p[j + 1] === '*') {
dp[i][j] = dp[i][j + 2] || (first && dp[i + 1][j]);
} else {
dp[i][j] = first && dp[i + 1][j + 1];
}
}
}
return dp[0][0];
}Edge cases to test
- A starred element that must match zero characters, like
a*against text with no a .*that could swallow the whole remaining text, but must leave some for later pattern parts- Pattern longer than the text because of starred parts, like s = "a", p = "bca"
- Text left over after the pattern is used up
Hints
Hint 1
Look at the pattern one element at a time, where an element is a single character or a character followed by *.
Hint 2
For x* you have two choices: skip it entirely, or (if the current text character matches x) consume one character and stay on x*.
Hint 3
The answer only depends on the pair (position in s, position in p), so there are at most (m + 1)(n + 1) distinct subproblems.
FAQ
What is the best time complexity for Regular Expression Matching?
Optimal (bottom-up DP table) runs in O(m · n) time and O(m · n) extra space. Each of the (m + 1)(n + 1) cells is filled once in O(1).
Which pattern does Regular Expression Matching use?
It is a dynamic programming problem that uses the strings pattern. Other problems with the same pattern: Edit Distance, Longest Common Subsequence, Longest Palindromic Subsequence.
Is there a brute force solution for Regular Expression Matching?
Yes. Brute force (plain recursion) takes O(2^(m + n)) in the worst case time and O(m + n) space. Define match(i, j) as whether s[i..] matches p[j..].
Which edge cases should I test for Regular Expression Matching?
A starred element that must match zero characters, like a against text with no a; . that could swallow the whole remaining text, but must leave some for later pattern parts; Pattern longer than the text because of starred parts, like s = "a", p = "bca"; Text left over after the pattern is used up.