首页 > 代码库 > Regular Expression Matching
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") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "a*") → trueisMatch("aa", ".*") → trueisMatch("ab", ".*") → trueisMatch("aab", "c*a*b") → true 基本思路就是先看字符串s和p的从i和j开始的子串是否匹配，用递归的方法直到串的最后，最后回溯回来得到结果。假设现在走到s的i位置，p的j位置，情况分为下列两种：
(1)p[j+1]不是‘*‘。情况比较简单，只要判断当前s的i和p的j上的字符是否一样（如果有p在j上的字符是‘.‘,也是相同），如果不同，返回false，否则，递归下一层i+1，j+1;
(2)p[j+1]是‘*‘。那么此时看从s[i]开始的子串，假设s[i],s[i+1],...s[i+k]都等于p[j]那么意味着这些都有可能是合适的匹配，那么递归对于剩下的(i,j+2),(i+1,j+2),...,(i+k,j+2)都要尝试（j+2是因为跳过当前和下一个‘*‘字符）。
C++实现代码如下：
#include<iostream>#include<string>using namespace std;class Solution {public: bool isMatch(const char *s, const char *p) { return helper(string(s),string(p),0,0); } bool helper(const string s,const string p,size_t i,size_t j) { if(j==p.length()) return i==s.length(); //p.charAt(j+1)!=‘*‘ if(j==p.length()-1||p[j+1]!=‘*‘) { if(i==s.length()||(s[i]!=p[j]&&p[j]!=‘.‘)) return false; else return helper(s,p,i+1,j+1); } //p.charAt(j+1)==‘*‘ while(i<s.length()&&(s[i]==p[j]||p[j]==‘.‘)) { if(helper(s,p,i,j+2)) return true; i++; } return helper(s,p,i,j+2); }};int main(){ Solution ss; const char *s="aa"; const char *p=".*bbb"; cout<<ss.isMatch(s,p)<<endl;}
Regular Expression Matching
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。