/**

* 10. 正则表达式匹配

*/

public class IsMatch {

public boolean isMatch(String s, String p) {

// 如果字符串长度为0，需要检测下正则串

if(s.length()==0){

// 如果正则串长度为奇数，必定不匹配，比如 "."、"ab*",必须是 a*b*这种形式，*在奇数位上

if(p.length()%2!=0){

return false;

}

for(int i=1; i<p.length();){

if(p.charAt(i)!='*'){

return false;

}

i+=2;

}

return true;

}

// 如果字符串长度不为0，但是正则串没了，return false

if(p.length()==0){

return false;

}

// c是正则串当前位的后一位，如果存在的话，就更新一下

char c = 'a';

if(p.length()>1){

c = p.charAt(1);

}

// 和dp一样，后一位分为是 '*' 和不是 '*' 两种情况

if(c!='*'){

// 如果该位字符一样，或是正则串该位是 '.',也就是能匹配任意字符，就可以往后走

if(s.charAt(0)==p.charAt(0) || p.charAt(0)=='.'){

return isMatch(s.substring(1), p.substring(1));

}else{

return false;

}

}else{

// 如果该位字符一样，或是正则串该位是 '.'，和dp一样，有看和不看两种情况

if(s.charAt(0)==p.charAt(0) || p.charAt(0)=='.'){

return isMatch(s.substring(1), p) || isMatch(s, p.substring(2));

}else{

// 不一样，那么正则串这两位就废了，直接往后走

return isMatch(s, p.substring(2));

}

}

}

}