题解 | #正则表达式匹配#
正则表达式匹配
https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4
自动机解法,需要保持Pattern的最简性,不然会超时。
#include <string> #include <unordered_map> #include <vector> struct Node{ char ch; bool star; Node* next; // vector<Node*> children; Node(char c){ ch = c; star = false; }; }; class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str string字符串 * @param pattern string字符串 * @return bool布尔型 */ Node* buildGraph(string pattern){ Node* start = new Node('S'); Node* head = start; Node* prev = start; for(int i=0;i<pattern.size();i++){ if((pattern[i]>='a'&&pattern[i]<='z')||(pattern[i]=='.')){ Node* next = new Node(pattern[i]); prev = head; head->next = next; head = head->next; } else if(pattern[i]=='*'){ if(head->ch==prev->ch&&prev->star){ prev->next = nullptr; head = prev; continue; } else head->star = true; } } Node* end = new Node('E'); head->next = end; return start->next; } bool matchGraph(string str, Node* pattern){ if((str.length()==0&&pattern->ch=='E')||(str.length()==0&&pattern->next->ch=='E'&&pattern->star)) return true; else if(str.length()==0) return false; else if(pattern->ch=='E') return false; if(pattern->ch=='.'){ if(pattern->star){ return (matchGraph(string(str.begin()+1, str.end()), pattern)||matchGraph(string(str.begin()+1, str.end()), pattern->next)||(matchGraph(string(str.begin(), str.end()), pattern->next))); } else{ return matchGraph(string(str.begin()+1, str.end()), pattern->next); } } else if(pattern->ch>='a' && pattern->ch<='z'&&str[0]==pattern->ch){ if(pattern->star){ return (matchGraph(string(str.begin()+1, str.end()), pattern)||matchGraph(string(str.begin()+1, str.end()), pattern->next)||(matchGraph(string(str.begin(), str.end()), pattern->next))); } else{ return matchGraph(string(str.begin()+1, str.end()), pattern->next); } } else if(pattern->ch>='a' && pattern->ch<='z'&&str[0]!=pattern->ch&&pattern->star){ return matchGraph(string(str.begin(), str.end()), pattern->next); } else{ return false; } } bool match(string str, string pattern) { // write code here auto patternGraph = buildGraph(pattern); // patternGraph = patternGraph->next; return matchGraph(str, patternGraph); } };