首页 > 代码库 > LeetCode Regular Expression Matching
LeetCode Regular Expression Matching
class Solution {#define SINGLE 1#define MULTIP 2public: bool isMatch(const char *s, const char *p) { if (s == NULL || p == NULL) return true; vector<pair<char, int> > pattern; int pos = 0; char ch = ‘\0‘; while ((ch = p[pos++]) != ‘\0‘) { if (ch == ‘*‘) { pattern.back().second = MULTIP; continue; } pattern.push_back(make_pair(ch, SINGLE)); } return isMatch(s, 0, pattern, 0); } bool isMatch(const char *s, int pos, vector<pair<char, int> > &pattern, int ppos) { if (ppos == pattern.size()) { return s[pos] == ‘\0‘; } int i = pos; pair<char, int> &p = pattern[ppos]; int offset = (p.second == SINGLE) ? 0 : -1; char ch = ‘\0‘; while (offset < 0 || (ch = s[pos + offset]) != ‘\0‘) { if (offset >= 0 && !cmp(ch, p.first)) { return false; } if (isMatch(s, pos + offset + 1, pattern, ppos + 1)) { return true; } if (p.second == SINGLE) break; offset++; } return false; } bool cmp(const char a, const char b) { if (a == ‘.‘ || b == ‘.‘) return true; return a == b; }};
暴力法, 216ms,
改写为记忆搜索,这里假设字符串和模式字符串的长度都不超过unsigned short 范围(6w+)， 84ms
class Solution {#define SINGLE 1#define MULTIP 2private: unordered_map<unsigned int, bool> memo;public: bool isMatch(const char *s, const char *p) { if (s == NULL || p == NULL) return true; memo.clear(); vector<pair<char, int> > pattern; int pos = 0; char ch = ‘\0‘; while ((ch = p[pos++]) != ‘\0‘) { if (ch == ‘*‘) { pattern.back().second = MULTIP; continue; } pattern.push_back(make_pair(ch, SINGLE)); } return isMatch(s, 0, pattern, 0); } bool isMatch(const char *s, int pos, vector<pair<char, int> > &pattern, int ppos) { unsigned int id = (pos << 16) | ppos; unordered_map<unsigned int, bool>::iterator iter = memo.find(id); if (memo.find(id) != memo.end()) return iter->second; bool res = false; if (ppos == pattern.size()) { res = s[pos] == ‘\0‘; memo.insert(make_pair(id, res)); return res; } int i = pos; pair<char, int> &p = pattern[ppos]; int offset = (p.second == SINGLE) ? 0 : -1; char ch = ‘\0‘; while (offset < 0 || (ch = s[pos + offset]) != ‘\0‘) { if (offset >= 0 && !cmp(ch, p.first)) { res = false; break; } if (isMatch(s, pos + offset + 1, pattern, ppos + 1)) { res = true; break; } if (p.second == SINGLE) break; offset++; } memo.insert(make_pair(id, res)); return res; } bool cmp(const char a, const char b) { if (a == ‘.‘ || b == ‘.‘) return true; return a == b; }};
LeetCode Regular Expression Matching
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。