在本文中，您将会了解到关于10.RegularExpressionMatching的新资讯，并给出一些关于*LeetCode10RegularExpressionMatching正则表达式、10Reg
在本文中，您将会了解到关于10. Regular Expression Matching的新资讯，并给出一些关于*LeetCode 10 Regular Expression Matching 正则表达式、10 Regular Expression Matching， 填dp table、10. Regular Expression Matching (JAVA)、10. Regular Expression Matching [H] 正则表达式匹配的实用技巧。
本文目录一览：- 10. Regular Expression Matching
- *LeetCode 10 Regular Expression Matching 正则表达式
- 10 Regular Expression Matching， 填dp table
- 10. Regular Expression Matching (JAVA)
- 10. Regular Expression Matching [H] 正则表达式匹配
10. Regular Expression Matching
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).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → truepublic class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) == ''*'' && dp[0][i - 1]) {
dp[0][i + 1] = true;
}
}
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) == ''.'') {
dp[i + 1][j + 1] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
dp[i + 1][j + 1] = dp[i][j];
}
if (p.charAt(j) == ''*'') {
if (p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != ''.'') { //match 0个的case，前一个字符跟当前不等
dp[i + 1][j + 1] = dp[i + 1][j - 1];
} else {
dp[i + 1][j + 1] = (dp[i + 1][j] || dp[i][j + 1] || dp[i + 1][j - 1]); //match 多个的情况
}
}
}
}
return dp[s.length()][p.length()];
}
}
*LeetCode 10 Regular Expression Matching 正则表达式
题目：
https://leetcode.com/problems/regular-expression-matching/
思路：
（1）DFS
（2）自动机
DFS版本写的比较烂，然后很长逻辑混乱，基本就是出bug补上。。。
592ms
const int DEBUG = 0;
class Solution {
public:
bool match(char a,char b) {
return (a == b || b == '.');
}
bool isMatch(string s,string p) {
if(dfs(s,p,0))
return true;
return false;
}
bool check(string p,int pos) {
if( (p.size()-pos) %2 == 0 ){
for(int i=1+pos; i<p.size(); i+=2)
if(p[i] != '*')return false;
return true;
}
return false;
}
bool dfs(string s,string p,int pos) {
if(s.size() == 0) {
/*if( (pos == p.size()&&p[pos-1]!='*' ||
(pos == p.size()-1 && p[pos]=='*'))
)return true;*/
if( (pos == p.size()&&p[pos-1]!='*' ||
(check(p,pos+1) && p[pos]=='*'))
)return true;
//if( (pos == p.size() || (check(p,pos) && p[pos]=='*')) )return true;
if(check(p,pos))return true;
if(DEBUG) {
cout << "s.size() == 0 s=" << s << " p=" << p << " pos=" << pos << endl;
}
return false;
}
if(p.size() <= pos) {
if(DEBUG) {
cout << "p.size() <= pos s=" << s << " p=" << p << " pos=" << pos << endl;
}
return false;
}
int ptrs = 0,ptrp = pos;
while(ptrs < s.size() && ptrp < p.size() ) {
if( match(s[ptrs],p[ptrp]) ) {
if(ptrp+2 < p.size() && p[ptrp+1] == '*') {
if(dfs(s.substr(ptrs),ptrp+2))return true;
}
ptrs ++,ptrp ++;
continue;
}
if(p[ptrp] == '*') {
if(ptrp >= 1) {
if( match(s[ptrs],p[ptrp-1]) ) {
return dfs(s.substr(ptrs+1),ptrp) | dfs(s.substr(ptrs),ptrp+1);
// | 1 | 0
} else {
return dfs(s.substr(ptrs),ptrp+1);
}
} else {
return false;
}
continue;
} //else {
if(ptrp+1 < p.size() && p[ptrp+1] == '*'){
//cout << "s=" << s.substr(ptrs) << " p=" << p << " " << ptrp+2 << endl;
return dfs(s.substr(ptrs),ptrp+2);
}
else
return false;
//}
}
if( ptrs >= s.size() ){
pos = ptrp;
//if( (pos == p.size()&&p[pos-1]!='*') || (pos == p.size()-1 && p[pos]=='*') )return true;
//if( (pos == p.size() || (check(p,pos) && p[pos]=='*')) )return true;
if( (pos == p.size()&&p[pos-1]!='*' ||
(check(p,pos+1) && p[pos]=='*'))
)return true;
if(check(p,pos))return true;
return false;
}
//if(ptrp >= p.size())return false;
return false;
}
};
正则表达式写法：很优雅，但是时间692ms，应该是因为某些可以用循环，但是这里还是递归了
class Solution {
public:
bool isMatch(string s,string p) {
return matchHere(s,p);
}
bool matchHere(string s,string p) {
if(s.size() == 0) {
return p.size()==0 || p.size()%2==0&&p[1]=='*'&&matchStar('\0',s,p.substr(2));
}
if(p.size() >=2 && p[1]=='*' && matchStar(p[0],p.substr(2)))
return true;
if(s[0] == p[0] || p[0] == '.') {
return matchHere(s.substr(1),p.substr(1));
}
return false;
}
//c* and p has erased c*
bool matchStar(char c,string s,string p){
int ptr = -1;
do {
++ptr;
if(matchHere(s.substr(ptr),p))return true;
} while( ptr<s.size() && ( s[ptr]==c || c=='.' ) );
return false;
}
};
正则表达式的写法参考：
http://hexlee.iteye.com/blog/552361
里面有^和&的处理方法
有空再去练习下怎么DFS写得优雅，比如http://blog.csdn.net/doc_sgl/article/details/12719761
10 Regular Expression Matching， 填dp table
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).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
public class Solution {
public boolean isMatch(String s, String p) {
// s.substring[0,i] matched p.substring[0,j]
boolean[][] matched = new boolean[s.length() + 1][p.length() + 1];
matched[0][0] = true;
for(int j=1; j<p.length(); j += 2){
if(p.charAt(j) == ''*'') {
matched[0][j+1] = matched[0][j-1]; //matched zero before
}
}
for(int i=1; i<=s.length(); i++){
for(int j=1; j<=p.length(); j++){
if(p.charAt(j-1) != ''*''){
matched[i][j] = matched[i-1][j-1] && isCharMatch(s.charAt(i-1), p.charAt(j-1));
} else {
// 解释清楚这两个条件是如何推导的。
// i,j-2 表示match zero char, i维持原位置，j位置的*，和j-1位置的char一同消失。
// i-1,j 表示match one char, s(i-1)和p(j-2)位置char是否相同.
matched[i][j] = matched[i][j-2] ||
matched[i-1][j] && isCharMatch(s.charAt(i-1), p.charAt(j-2));
}
}
}
return matched[s.length()][p.length()];
}
public boolean isCharMatch(char s, char p){
return p == ''.'' || s == p;
}
}s = "ab" p = ".*"
. *
T F T
a F T T
b F F T
10. Regular Expression Matching (JAVA)
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 precedeng 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
class Solution {
public boolean isMatch(String s, String p) {
return recur(s,p,0,0);
}
public boolean recur(String s, String p, int sPtr, int pPtr) {
if(s.length() == sPtr && p.length() == pPtr) return true;
if(p.length() == pPtr) return false;
if(s.length() == sPtr){
if(p.length() > pPtr+1 && p.charAt(pPtr+1)==''*'') return recur(s,p,sPtr,pPtr+2);
else return false;
}
if(p.length() > pPtr+1 && p.charAt(pPtr+1)==''*''){ //next bit is *
if(recur(s,p,sPtr,pPtr+2)) return true; //* match 0 element
else{
for(int i = 1; sPtr + i <= s.length() && (p.charAt(pPtr)==s.charAt(sPtr+i-1)|| p.charAt(pPtr)==''.''); i++){
if(recur(s,p,sPtr+i,pPtr+2)) return true; //* match i elements
}
}
}
else if(p.charAt(pPtr)==''.'' || p.charAt(pPtr)==s.charAt(sPtr))
return recur(s, p, sPtr+1, pPtr+1);
return false;
}
}当当前字符之后的那个字符是 * 时，我们需要对当前字符做特别判断，所以没次递归中要判断 p 字符串的下一个字符是否是 *
![10. Regular Expression Matching [H] 正则表达式匹配](http://www.gvkun.com/zb_users/upload/2025/02/dc80873c-84bb-4a36-96dd-6db7af099f241739666449725.jpg "10. Regular Expression Matching [H] 正则表达式匹配")
10. Regular Expression Matching [H] 正则表达式匹配
#题目
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 . or * .
Example1： Input：s = "aa" p="a" Output：false Explanation："a" does not match the entire string "a" Example2： Input：s = "aa" p="a*" Output：true Explanation：".*" means zero or more of the precedeng element, ''a''. Therefore, by repeating ''a'' once, it become "a".
Example3： Input：s = "ab" p=".*" Output：true Explanation："." means " zero or more () of any character (.) " . #思路
### 动态规划 #####Step1. 刻画一个最优解的结构特征 $dp [i][j]$ 表示 $s [0,\cdots,i-1]$ 与 $p [0,\cdots,j-1]$ 是否匹配 #####Step2. 递归定义最优解的值 1.$p [j-1] == s [i-1]$，则状态保存，$dp [i][j] = dp [i-1][j-1]$ 2.$p [j-1] ==$ .，. 与任意单个字符匹配，于是状态保存，$dp [i][j] = dp [i-1][j-1]$ 3.$p [j-1] == $*，* 只能以 X* 的形式才能匹配，但是由于 * 究竟作为几个字符匹配不确定，此时有两种情况：
- $p [j-2] != s [i-1]$，此时 $s [0,\cdots,i-1]$ 与 $p [0,\cdots,j-3]$ 匹配，即 $dp [i][j] = dp [i][j-2]$
- $p [j-2] == s [i-1]$ 或者 $p [j-2] == $
.，此时应分为三种情况：*作为零个字符，$dp [i][j] = dp [i][j-2]$*作为一个字符，$dp [i][j] = dp [i][j-1]$*作为多个字符，$dp [i][j] = dp [i-1][j]$
#####Step3. 计算最优解的值 根据状态转移表，以及递推公式，计算 dp [i][j]
#Tips
### 数组初始化（python） #####（1）相同的值初始化 (一维数组)
#方法一：list1 = [a a a ]
list1 = [ a for i in range(3)]
#方法二:
list1 = [a] * 3
#####（2）二维数组初始化 初始化一个 $4*3$ 每项固定为 0 的数组
list2 = [ [0 for i in range(3)] for j in range(4)]
#C++
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(),n = p.length();
bool dp[m+1][n+1];
dp[0][0] = true;
//初始化第0行,除了[0][0]全为false，因为空串p只能匹配空串，其他都无能匹配
for (int i = 1; i <= m; i++)
dp[i][0] = false;
//初始化第0列，只有X*能匹配空串
for (int j = 1; j <= n; j++)
dp[0][j] = j > 1 && ''*'' == p[j - 1] && dp[0][j - 2];
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if (p[j - 1] == ''*'')
{
dp[i][j] = dp[i][j - 2] || (s[i - 1] == p[j - 2] || p[j - 2] == ''.'') && dp[i - 1][j];
}
else //只有当前字符完全匹配，才能传递dp[i-1][j-1] 值
{
dp[i][j] = (p[j - 1] == ''.'' || s[i - 1] == p[j - 1]) && dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
};
#Python
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
len_s = len(s)
len_p = len(p)
dp = [[False for i in range(len_p+1)]for j in range(len_s+1)]
dp[0][0] = True
for i in range(1, len_p + 1):
dp [0][i] = i>1 and dp[0][i - 2] and p[i-1] == ''*''
for i in range (1, len_s + 1 ):
for j in range(1, len_p + 1):
if p[j - 1] == ''*'':
#状态保留
dp[i][j] = dp[i][j -2] or (s[i-1] == p[j-2] or p[j-2] == ''.'') and dp[i-1][j]
else:
dp[i][j] = (p[j-1] == ''.'' or s[i-1] == p[j-1]) and dp[i-1][j-1]
return dp[len_s][len_p]
今天关于10. Regular Expression Matching的讲解已经结束，谢谢您的阅读，如果想了解更多关于*LeetCode 10 Regular Expression Matching 正则表达式、10 Regular Expression Matching， 填dp table、10. Regular Expression Matching (JAVA)、10. Regular Expression Matching [H] 正则表达式匹配的相关知识，请在本站搜索。
本文标签：
