题目
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
解题思路
直接实现一个有限状态机，完成对这题目的题解。这里需要实现有向图和DFS搜索算法。同时还需要一个栈来处理嵌套的正则表达式。目前我实现了以下的正则表达式语法：
- 正常字符串；
- '*'语法；
- '.'语法；
- AB语法；
- (A|B)语法。
以下是C++代码:
C++解法
class Stack {
private:
vector<int> elems;
public:
void push(int const& elem) {
elems.push_back(elem);
}
int pop() {
if (elems.empty()) throw out_of_range("Stack<>::pop(): empty stack");
int back = elems.back();
elems.pop_back();
return back;
}
int top() const {
if (elems.empty()) throw out_of_range("Stack<>::top(): empty stack");
return elems.back();
}
bool empty() const {
return elems.empty();
}
};
class DiGraph {
public:
DiGraph(int v): V(v), adj(V, vector<int>()), E(0) {}
void addEdge(int v, int w) {
adj[v].push_back(w);
++E;
}
int vector_size() {return V;}
int edge_size() {return E;}
vector<int> adjacent(int v) {return adj[v];}
private:
int V;
int E;
vector<vector<int>> adj;
};
class DirectedDFS {
public:
DirectedDFS(DiGraph G, int s) : marked(G.vector_size()) {
dfs(G, s);
}
DirectedDFS(DiGraph G, vector<int> & sources) : marked(G.vector_size()) {
for (int s: sources){
if (!marked[s]) dfs(G, s);
}
}
void dfs(DiGraph G, int v) {
marked[v] = true;
for (int w: G.adjacent(v)) {
if (!marked[w]) dfs(G, w);
}
}
bool is_marked(int v) { return marked[v];}
private:
vector<bool> marked;
};
class NFA {
public:
DiGraph G;
NFA(string regexp): re(regexp), M((int)regexp.size()), G((int)regexp.size() + 1) {
Stack ops;
for (int i = 0; i < M; i++) {
int lp = i;
if (re[i] == '(' || re[i] == '|') ops.push(i);
else if (re[i] == ')') {
int or_value = ops.pop();
if (re[or_value] == '|') {
lp = ops.pop();
G.addEdge(lp, or_value + 1);
G.addEdge(or_value, i);
} else lp = or_value;
}
if (i < M - 1 && re[i + 1] == '*') {
G.addEdge(lp, i + 1);
G.addEdge(i + 1, lp);
}
if (re[i] == '(' || re[i] == '*' || re[i] == ')') G.addEdge(i, i+1);
}
}
bool recognizes(string txt) {
vector<int> pc;
DirectedDFS dfs(G, 0);
for (int v = 0; v < G.vector_size(); v++)
if (dfs.is_marked(v)) pc.push_back(v);
for (int i = 0; i < txt.length(); i++) {
vector<int> match;
for (int v: pc) {
if (v < M) {
if (re[v] == txt[i] || re[v] == '.') {
match.push_back(v+1);
}
}
}
pc = vector<int>();
dfs = DirectedDFS(G, match);
for (int v = 0; v < G.vector_size(); v++)
if(dfs.is_marked(v)) pc.push_back(v);
}
for (int v: pc) if (v == M) return true;
return false;
}
private:
int M;
string re;
};
class Solution {
public:
bool isMatch(string s, string p) {
return NFA(p).recognizes(s);
}
};
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regular-expression-matching
