Wildcard pattern-matching algorithm

Question

I was trying to write code which does a validation for the below wildcards:

• '?' ------> The question mark indicates there is zero or one of the preceding element. For example, colou?r matches both "color" and "colour".

• '*' ------> The asterisk indicates there is zero or more of the preceding element. For example, ab*c matches "ac", "abc", "abbc", "abbbc", and so on.

• '+' ------> The plus sign indicates there is one or more of the preceding element. For example, ab+c matches "abc", "abbc", "abbbc", and so on, but not "ac".

I know that Java does provide pattern matching with wild cards out of box, but this is more of an exercise to understand the crux by not using libraries.

static boolean matches(String pattern, String text) {
    if (text == null && pattern == null) {
        return true;
    }
    if (text == null || pattern == null) {
        return false;
    }
    if (text.equals(EMPTY_STRING) && pattern.equals(EMPTY_STRING)) {
        return true;
    }
    if (text.equals(EMPTY_STRING) || pattern.equals(EMPTY_STRING)) {
        return false;
    }
    char[] p = pattern.toCharArray();
    char[] t = text.toCharArray();
    int indexP1 = 0, indexP2 = 1, indexT = 0;
    while (true) {
        if (indexP1 == p.length && indexT == t.length){
            return true;
        } else if (indexP1 == p.length || indexT == t.length){
            return false;
        } else {
            if (indexP2 < p.length && p[indexP2] == '*'){//case: a*
                while (t[indexT] == p[indexP1]) {
                    indexT++;
                    if(indexT==t.length)break;
                }
                indexP1 = indexP1 + 2;
                indexP2 = indexP2 + 2;
            }
            else if (indexP2 < p.length && p[indexP2] == '+') {//case: a+
                if(t[indexT] != p[indexP1]){
                    return false;
                }
                while (t[indexT] == p[indexP1]) {
                    indexT++;
                    if(indexT==t.length)break;
                }
                indexP1 = indexP1 + 2;
                indexP2 = indexP2 + 2;
            }
            else if (indexP2 < p.length && p[indexP2] == '?') {//case: a?
                if (t[indexT] == p[indexP1]) {
                    indexT++;
                }
                indexP1 += 2;
                indexP2 += 2;
            } else {//case: a
                if (t[indexT] != p[indexP1]) {
                    return false;
                }
                indexP1++;
                indexP2++;
                indexT++;
            }
        }
    }
}

Answer 1

Right away, I see two bugs:

First, it is not valid to say

if (text.equals(EMPTY_STRING) || pattern.equals(EMPTY_STRING)) {
    return false;
}

… because a non-empty pattern can certainly match an empty string.

Second, it takes a state machine to do regular expression matching properly; all I saw in your code were a few pointers. (What are indexP1, indexP2, and indexT supposed to stand for? Is there some invariant stateabout them that you could write out in a comment?) It seems that you are matching * and + greedily. That can't be right; sometimes you might need to backtrack and consider another possibility in order to get a match.

I didn't analyze the code too deeply, but those two serious concerns suggest that you will need to work at this code a lot more anyway.