public class Solution {
    public boolean isMatch(String s, String p) {
        //simple match
        if(p.length()==0&&s.length()>0)return false;
        if(p.length()==0&&s.length()==0)return true;
        if(s.length()==0){
            if(p.length()>1&&p.charAt(1)=='*')
                return isMatch(s,p.substring(2));
            else return false;
        }

        // p and s must has length great than 0 from here  
        if(p.length()==1){
            if(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.')
                return isMatch(s.substring(1),p.substring(1));
            else return false;
        }else{
            if(p.charAt(1)=='*'){
                if(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.')
                    return isMatch(s.substring(1),p.substring(0))||
                        isMatch(s.substring(0),p.substring(2));
                else
                    return isMatch(s.substring(0),p.substring(2));
            }else{
                if(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.')
                    return isMatch(s.substring(1),p.substring(1));
                else return false;
            }
        }
    }
}