每天一道剑指offer-正则表达式匹配
正则表达式匹配
题目描述
请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
public boolean match(char[] str, char[] pattern){
}解析
使用 p1指向 str中下一个要匹配的字符，使用 p2指向 pattern中剩下的模式串的首字符
- 如果
p2>=pattern.length，表示模式串消耗完了，这时如果p1仍有字符要匹配那么返回false否则返回true - 如果
p1>=str.length，表示要匹配的字符都匹配完了，但模式串还没消耗完，这时剩下的模式串必须符合a*b*c*这样的范式以能够作为空串处理，否则返回false p1和p2都未越界，按照p2后面是否是*来讨论p2后面如果是*，又可按照pattern[p2]是否能够匹配str[p1]分析：pattern[p2]==‘.’||pattern[p2]==str[p1]，这时可以选择匹配一个str[p1]并继续向后匹配（不用跳过p2和其后面的*），也可以选择将pattern[p2]和其后面的*作为匹配空串处理，这时要跳过p2和 其后面的*pattern[p2]!=str[p1]，只能作为匹配空串处理，跳过p2
p2后面如果不是*：pattern[p2]==str[p1]||pattern[p2]==‘.’，p1,p2同时后移一个继续匹配pattern[p2]==str[p1]，直接返回false
public boolean match(char[] str, char[] pattern){ if(str == null || pattern == null){ return false; } if(str.length == 0 && pattern.length == 0){ return true; } return matchCore(str, 0, pattern, 0);}
public boolean matchCore(char[] str, int p1, char[] pattern, int p2){ //模式串用完了 if(p2 >= pattern.length){ return p1 >= str.length; } if(p1 >= str.length){ if(p2 + 1 < pattern.length && pattern[p2 + 1] == '*'){ return matchCore(str, p1, pattern, p2 + 2); }else{ return false; } }
//如果p2的后面是“*” if(p2 + 1 < pattern.length && pattern[p2 + 1] == '*'){ if(pattern[p2] == '.' || pattern[p2] == str[p1]){ //匹配一个字符，接着还可以向后匹配；或者将当前字符和后面的星合起来做空串 return matchCore(str, p1 + 1, pattern, p2) || matchCore(str, p1, pattern, p2 + 2); }else{ return matchCore(str, p1, pattern, p2 + 2); } } //如果p2的后面不是* else{ if(pattern[p2] == '.' || pattern[p2] == str[p1]){ return matchCore(str, p1 + 1, pattern, p2 + 1); }else{ return false; } }}出自：http://www.zhenganwen.top
已获授权
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-02-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
