先来题目：
‘.‘ 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
Hmm 关于这道题 刚开始看到题的时候对我来说 首先大体的思路很容易就出来了。 然后就是大概的框架也有了。
主要就是情况要分清楚。关于‘.‘和‘*’的用法 以及几种特殊情况。 另外刚开始，我完全没有察觉可以直接用imatch然后我就一直在想怎么match啊怎么match啊哈哈
答案仅供参考啊0.0主要还是逻辑问题 要分清楚case最重要
public class Solution {
public boolean isMatch(String s, String p) {
//easy to think about
if(p.length()==0){
return s.length()==0;
}
//special case
if(p.length()==1){
if(s.length()<1){
return false;
}
else if((s.charAt(0)!=p.charAt(0))&&(p.charAt(0)!=‘.‘)){
return false;
}
else{
return isMatch(s.substring(1),p.substring(1));
}
}
//easy to write, hard to think
if(p.charAt(1)!=‘*‘){
if(s.length()<1){
return false;
}
else if((p.charAt(0)!=s.charAt(0))&&(p.charAt(0)!=‘.‘)){
return false;
}else{
return isMatch(s.substring(1),p.substring(1));
}
}
//most difficult one
else{
if(isMatch(s,p.substring(2))){
return true;
}
int i=0;
while(i<s.length()&&(s.charAt(i)==p.charAt(0)||p.charAt(0)==‘.‘)){
if(isMatch(s.substring(i+1),p.substring(2))){
return true;
}
i++;
}
return false;
}
}
}
LeetCode Notes Regular Expression Matching
原文：http://www.cnblogs.com/orangeme404/p/4718492.html