Вот непроверенный код. Идея в том, что мы отслеживаем, где мы находимся в строке и шаблоне. Это НЕ будет хорошим подходом к расширению до полного движка RE (просто подумайте, что может потребоваться при добавлении скобок), но для этого случая хорошо:
public static boolean isMatch (String p, String s, int pos_p, int pos_s) {
if (pos_p == p.length()) {
// We matched the whole pattern.
return true;
}
else if (pos_s == s.length()) {
// We reached the end of the string without matching.
return false;
}
else if (pos_p == -1) {
// Do we match the pattern starting next position?
if (isMatch(p, s, pos_p + 1, pos_s + 1)) {
return true;
}
else {
// Try to match the pattern starting later.
return isMatch(p, s, pos_p, pos_s + 1);
}
}
else {
char thisCharP = p.charAt(pos_p);
char nextCharP = pos_p + 1 < p.length() ? p.charAt(pos_p + 1) : 'x';
// Does this character match at this position?
boolean thisMatch = (thisCharP == s.charAt(pos_s));
if (thisCharP == '.') {
thisMatch = true;
}
if (nextCharP == '*') {
// Try matching no times - we don't need thisMatch to be true!
if (isMatch(p, s, pos_p + 2, pos_s)) {
return true;
}
else {
// Try matching 1+ times, now thisMatch is required.
return thisMatch && isMatch(p, s, pos_p, pos_s + 1);
}
}
else if (nextCharP == '+') {
if (! thisMatch) {
// to match 1+, we have to match here.
return false;
}
else if (isMatch(p, s, pos_p + 2, pos_s + 1)) {
// We matched once.
return true;
}
else {
// Can we match 2+?
return isMatch(p, s, pos_p, pos_s + 1);
}
}
else if (thisMatch) {
// Can we match the rest of the pattern?
return isMatch(p, s, pos_p + 1, pos_s + 1);
}
else {
// We didn't match here, this is a fail.
return false;
}
}
}
public static boolean isMatch (String p, String s) {
// Can we match starting anywhere?
return isMatch(p, s, -1, -1);
}