1public class Solution {
2 public boolean isMatch(String s, String p) {
3
4 if(p.length() == 0)
5 return s.length() == 0;
6
7 //p's length 1 is special case
8 if(p.length() == 1 || p.charAt(1) != '*'){
9 if(s.length() < 1 || (p.charAt(0) != '.' && s.charAt(0) != p.charAt(0)))
10 return false;
11 return isMatch(s.substring(1), p.substring(1));
12
13 }else{
14 int len = s.length();
15
16 int i = -1;
17 while(i<len && (i < 0 || p.charAt(0) == '.' || p.charAt(0) == s.charAt(i))){
18 if(isMatch(s.substring(i+1), p.substring(2)))
19 return true;
20 i++;
21 }
22 return false;
23 }
24 }
25}