> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/graph-search/10.regular-expression-matching.md).
# 10.Regular-Expression-Matching
## 10. Regular Expression Matching
## 题目地址
## 题目描述
```
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.
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 (.)".
Example 4:
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example 5:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
```
## 代码
### Approach 1: Recursion
从左到右substring text和pattern
```java
public boolean isMatch(String text, String pattern) {
if (pattern.isEmpty()) return text.isEmpty();
boolean first_match = (!text.isEmpty()
&& (pattern.charAt(0) == text.charAt(0)
|| pattern.charAt(0) == '.'));
//只有长度大于 2 的时候，才考虑 *
if (pattern.length() >= 2 && pattern.charAt(1) == '*') {
//两种情况
//pattern 直接跳过两个字符。表示 * 前边的字符出现 0 次
//pattern 不变，例如 text = aa ，pattern = a*，第一个 a 匹配，然后 text 的第二个 a 接着和 pattern 的第一个 a 进行匹配。表示 * 用前一个字符替代。
return (isMatch(text, pattern.substring(2)) ||
(first_match && isMatch(text.substring(1), pattern)));
} else {
return first_match && isMatch(text.substring(1), pattern.substring(1));
}
}
```
### Approach #2 DP - Bottom - up
dp\[ i ] \[ j ] = 表示 text 从 i 开始到最后，pattern 从 j 开始到最后，此时 text 和 pattern 是否匹配。
```java
1, If p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i + 1][j + 1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i + 1][j + 1];
3, If p.charAt(j + 1) == '*':
here are two sub conditions:
dp[i][j] = first_match && dp[i + 1][j] // in this case, a* counts as multiple a
dp[i][j] = first_match && dp[i + 1][j + 1]; // in this case, a* counts as single a
dp[i][j] = dp[i][j + 2] // in this case, a* counts as empty
```
```java
public boolean isMatch(String text, String pattern) {
// 多一维的空间，因为求 dp[len - 1][j] 的时候需要知道 dp[len][j] 的情况，
// 多一维的话，就可以把 对 dp[len - 1][j] 也写进循环了
boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
// dp[len][len] 代表两个空串是否匹配了，"" 和 "" ，当然是 true 了。
dp[text.length()][pattern.length()] = true;
// 从 len 开始减少
for (int i = text.length(); i >= 0; i--) {
for (int j = pattern.length(); j >= 0; j--) {
// dp[text.length()][pattern.length()] 已经进行了初始化
if (i == text.length() && j == pattern.length()) continue;
boolean first_match = (i < text.length() && j < pattern.length()
&& (pattern.charAt(j) == text.charAt(i)
|| pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {
// 跳过pattern || 匹配一个，继续往下匹配该pattern
dp[i][j] = dp[i][j + 2] || first_match && dp[i + 1][j];
} else {
// 逐个匹配
dp[i][j] = first_match && dp[i + 1][j + 1];
}
}
}
return dp[0][0];
}
```
### Approach #3 Dynamic Programming
`dp[i][j]` denotes if s.substring(0,i) is valid for pattern `p.substring(0,j)`.
For example `dp[0][0] == true` (denoted by y in the matrix) because when s and p are both empty they match. So if we somehow base `dp[i+1][j+1]` on previos `dp[i][j]`'s then the result will be `dp[s.length()][p.length()]`
```java
class Solution {
public boolean isMatch(String s, String p) {
if (p == null || p.length() == 0) return (s == null || s.length() == 0);
boolean dp[][] = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true;
for (int j = 1; j < p.length(); j += 2) {
// 匹配空串，a*b*c*.. 各匹配0次
dp[0][j + 1] = p.charAt(j) == '*' && dp[0][j - 1];
}
// 从 (1, 1) 开始
for (int j = 1; j <= p.length(); j++) {
for (int i = 1; i <= s.length(); i++) {
if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.') {
// 各移动比较一次
dp[i][j] = dp[i - 1][j - 1];
} else if(p.charAt(j - 1) == '*') {
// 0 次匹配 || 匹配一次（first match && 前i-1匹配）
dp[i][j] = dp[i][j - 2] || ((s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') && dp[i - 1][j]);
}
}
}
return dp[s.length()][p.length()];
}
}
```
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:
```
GET https://wentao-shao.gitbook.io/leetcode/graph-search/10.regular-expression-matching.md?ask=&goal=
```
`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.