LeetCode--Regular Expression Matching
发布时间:2020-12-14 01:27:50 所属栏目:百科 来源:网络整理
导读: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
Implement regular expression matching with support for '.' 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]!=' ' && p[i] != ' ') { if(s[i]=='.' || p[i]=='.') { i++; continue; } if(s[i] != p[i]) return false; i++; } if(s[i]!=' ' || p[i]!=' ') 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] != ' ') { if(s[i] == '*') return true; i++; } return false; } string char_to_string(const char* s) { string temp = ""; int i=0; while(s[i] != ' ') { temp = temp + s[i]; i++; } return temp; } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |