首页 > 其他 > 详细

【leetcode刷题笔记】Regular Expression Matching

时间:2014-07-26 01:37:06      阅读:352      评论:0      收藏:0      [点我收藏+]

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") → 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

题解:又见递归的解法。这道题交了好多次,主要是细节要想清楚。总结一下要注意的地方:

  • 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位是否是‘*’了。处理这一段代码如下:
  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 match
25                 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 trying
30             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 it
38             return isMatch(s, p.substring(2));
39         }
40     }
41 }

 

【leetcode刷题笔记】Regular Expression Matching,布布扣,bubuko.com

【leetcode刷题笔记】Regular Expression Matching

原文:http://www.cnblogs.com/sunshineatnoon/p/3869055.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!