Why this can’t be done in O(n):
class RegxMatch {
static boolean regxMatch(String text, String pattern) {
int i = pattern.length() - 1;
int j = text.length() - 1;
if (text.isEmpty() && pattern.isEmpty())
return true;
if (pattern.isEmpty())
return true;
while (i > -1 && j > -1) {
char curPatCh = pattern.charAt(i);
// if *
if (curPatCh == '*') {
i--;
curPatCh = pattern.charAt(i);
while(i>0 && curPatCh == pattern.charAt(i-1) ) {
curPatCh = pattern.charAt(--i);
}
// if .
if (curPatCh == '.') {
char prev = text.charAt(j - 1);
while (j >= 0 && j>=i && text.charAt(j) == prev) {
j--;
}
} else {
// other character
while (j >= 0 && j >=i && text.charAt(j) == curPatCh) {
j--;
}
}
i--;
}
// if .
else if (curPatCh == '.') {
i--;
j--;
}
// any other character
else {
if (text.charAt(j) != curPatCh)
return false;
i--;
j--;
}
}
if (i != -1 || j != -1)
return false;
return true;
}
}