[LeetCode76]Regular Expression Matching
发布时间:2020-12-14 01:44:47 所属栏目:百科 来源:网络整理
导读: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 Analysis:
待匹配串为S,匹配串为P。 回到原问题,对于S[i]和P[j]: c++
bool isMatch(const char *s,const char *p) { if(*p==' ') return *s ==' '; //next char is not '*':must match current character if(*(p+1)!='*'){ return ((*p==*s)||(*p=='.'&& *s!=' ')) && isMatch(s+1,p+1); } //next char is '*' while((*p==*s)||(*p=='.' && *s!=' ')){ if(isMatch(s,p+2)) return true; s++; } return isMatch(s,p+2); } 确定了递归以后,使用java来实现这个问题,会遇到很多和c不一样的地方,因为java对字符 的控制不像c语言指针那么灵活charAt一定要确定某个位置存在才可以使用. 如果pattern是"x*"类型的话,那么pattern每次要两个两个的减少.否则,就是一个一个 的减少. 无论怎样减少,都要保证pattern有那么多个.比如s.substring(n),其中n 最大也就是s.length()
public boolean isMatch(String s,String p) { if(p.length()==0) return s.length()==0; if(p.length()==1) return (s.length()==1)&&(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.'); if(p.charAt(1)!='*'){ if(s.length()==0) return false; else { return (s.charAt(0)==p.charAt(0) || p.charAt(0)=='.') && isMatch(s.substring(1),p.substring(1)); } }else { while(s.length()>0 && (p.charAt(0)==s.charAt(0)||p.charAt(0)=='.')){ if(isMatch(s,p.substring(2))) return true; s = s.substring(1); } return isMatch(s,p.substring(2)); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |