首页 > 代码库 > LeetCode--Regular Expression Matching
LeetCode--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") → true
本题使用了正则表达式匹配的方法,用非确定状态自动机模拟字符串p,从而进行字符串的匹配,算法的时间复杂度为O(N);解题代码:
class graph { private: struct node { int wei; node* next; }; node* g; int v; bool* marked; void dfs(const int s) { marked[s] = true; vector<int> temp = adj(s); for(int i=0; i<temp.size(); i++) { if(!marked[temp[i]]) dfs(temp[i]); } return ; } public: graph(const int v) { this->v = v; marked = new bool[v]; g = new node[v]; for(int i=0; i<v; i++) { marked[i] = false; g[i].wei = 0; g[i].next = nullptr; } } ~graph() { delete[] marked; for(int i=0; i<v; i++) { node* temp1 = g[i].next; while(temp1!=nullptr) { node* temp2 = temp1; temp1 = temp1->next; delete temp2; } } delete[] g; } bool is_marked(const int v){ return marked[v];} void restore_marked() { for(int i=0; i<v; i++) marked[i] = false; } void add_edge(const int v, const int w) { node* temp = new node; temp->wei = w; temp->next = g[v].next; g[v].next = temp; } void dfs(vector<int>& start) { int n = start.size(); for(int i=0; i<n; i++) if(!marked[start[i]]) dfs(start[i]); } vector<int>& adj(const int v) { vector<int>* res = new vector<int>; node* temp = g[v].next; while(temp!=nullptr) { res->push_back(temp->wei); temp = temp->next; } return *res; } }; class Solution { public: bool isMatch(const char *s, const char *p) { if(has_star(p)) return match(s,p); int i=0; while(s[i]!='\0' && p[i] != '\0') { if(s[i]=='.' || p[i]=='.') { i++; continue; } if(s[i] != p[i]) return false; i++; } if(s[i]!='\0' || p[i]!='\0') return false; return true; } bool match(const char* s, const char* p) { string temp_s = char_to_string(s); string temp_p = char_to_string(p); int n = temp_p.length(); graph g(n+1); for(int i=0; i<n; i++) { if(p[i] == '*') { g.add_edge(i,i-1); g.add_edge(i-1,i); g.add_edge(i,i+1); } } vector<int> pc; vector<int> marked; marked.push_back(0); g.dfs(marked); for(int i=0; i<n+1; i++) { if(g.is_marked(i)) pc.push_back(i); } for(int i=0; i<temp_s.length(); i++) { marked.clear(); for(int v=0; v<pc.size(); v++) { if(pc[v]<n) { if(p[pc[v]] == s[i] || p[pc[v]] == '.') marked.push_back(pc[v]+1); } } pc.clear(); g.restore_marked(); g.dfs(marked); for(int i=0; i<n+1; i++) { if(g.is_marked(i)) pc.push_back(i); } } for(int i=0; i<pc.size(); i++) { if(pc[i] == n) return true; } return false; } bool has_star(const char* s) { int i=0; while(s[i] != '\0') { if(s[i] == '*') return true; i++; } return false; } string char_to_string(const char* s) { string temp = ""; int i=0; while(s[i] != '\0') { temp = temp + s[i]; i++; } return temp; } };
LeetCode--Regular Expression Matching
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。