首页 > 代码库 > 【leetcode刷题笔记】Regular Expression Matching
【leetcode刷题笔记】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为0的时候,如果p为1,false;否则如果p的第1位上为‘*‘,那么就要考察p后面的元素,于是递归调用 isMatch(s, p.substring(2)) ,这样的例子有s = "", p = "c*c*";如果p的第一位上不为1,那么s和p肯定不匹配了。
- 当p长度为1的时候要单独处理,因为这时候我们不用判断p的第1位是否是‘*’了。处理这一段代码如下:
if(p.length() == 1){ if(p.charAt(0) == ‘.‘ && s.length() == 1) return true; return s.equals(p);}
- 其他情况就要按照p的第1位是否为‘*‘来分了。如果不为’*‘,那么p和s的第0位必须匹配(相等或p第0位为‘.‘),否则p和s不匹配,这样的例子类似的有s = "ab", p = "c*b"。如果为‘*‘,我们就按照匹配0位,1位,2位.....的方式递归试探,类似的例子有s = "abbc", p = "ab*bbc",此时‘*‘并不匹配s中的任何字符,再有s = "aa",p = "a*",此时‘*‘匹配s中的两个a。
代码如下:
1 public class Solution { 2 public boolean isMatch(String s, String p) { 3 if(p.length() == 0) 4 return s.length() == 0; 5 6 if(s.length() == 0){ 7 if(p.length() == 1) 8 return false; 9 if(p.charAt(1) == ‘*‘)10 return isMatch(s, p.substring(2));11 return false;12 }13 14 15 if(p.length() == 1){16 if(p.charAt(0) == ‘.‘ && s.length() == 1)17 return true;18 return s.equals(p);19 }20 21 if(p.length() >= 2 && p.charAt(1) != ‘*‘){22 //if p(1) is not *, we need p(0) equals to s(0) or p(0) equals ‘.‘23 if(p.charAt(0) == s.charAt(0) || p.charAt(0) == ‘.‘ && s.length() != 0)24 //check if the left is also match25 return isMatch(s.substring(1), p.substring(1));26 return false;27 }28 else{29 //if p(1) is ‘*‘,we check how many we can match from this * by trying30 int i = 0;31 char now = p.charAt(0);32 while(i<s.length() && (s.charAt(i) == now || now == ‘.‘)){33 if(isMatch(s.substring(i+1),p.substring(2)))34 return true;35 i++;36 }37 //this means we don‘t use this ‘*‘ to match any character, just skip it38 return isMatch(s, p.substring(2));39 }40 }41 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。