Daily Archives: October 25, 2015

This post responds to junmin’s code: link

Below is my recursion implementation for ‘?’ and ‘*’ regular expression match:

public static boolean matchReg(String str, String reg) {
    return matchRegUtil(str, 0, reg, 0);
}

public static boolean matchRegUtil(String str, int strPos, String reg, int regPos) {
    if(strPos>=str.length() && regPos>=reg.length()) {
        return true;
    }
    else if(regPos>=reg.length()) {
        return false;
    }
    else if(strPos>=str.length()) {
        for(int i=regPos; iif(reg.charAt(i)!='*') {
                return false;
            }
        }
        return true;
    }
    if(reg.charAt(regPos)==str.charAt(strPos)||reg.charAt(regPos)=='?') {
        return matchRegUtil(str, strPos+1, reg, regPos+1);
    }
    else if(reg.charAt(regPos)=='*'){
        for(int i=strPos-1; iif(matchRegUtil(str, i+1, reg, regPos+1)) {
                return true;
            }
        }
    }
    return false;
}