Finding whether a string meets a certain pattern

Question

I recently had an interview with Google for a Software Engineering position and the question asked regarded building a pattern matcher.

So you have to build the

boolean isPattern(String givenPattern, String stringToMatch)

Function that does the following:

givenPattern is a string that contains:

a) 'a'-'z' chars
b) '*' chars which can be matched by 0 or more letters
c) '?' which just matches to a character - any letter basically

So the call could be something like

isPattern("abc", "abcd") - returns false as it does not match the pattern ('d' is extra)

isPattern("a*bc", "aksakwjahwhajahbcdbc"), which is true as we have an 'a' at the start, many characters after and then it ends with "bc"

isPattern("a?bc", "adbc") returns true as each character of the pattern matches in the given string.

During the interview, time being short, I figured one could walk through the pattern, see if a character is a letter, a * or a ? and then match the characters in the given string respectively. But that ended up being a complicated set of for-loops and we didn't manage to come to a conclusion within the given 45 minutes.

Could someone please tell me how they would solve this problem quickly and efficiently?

Many thanks!

Answer 1

Assuming you are allowed to use regexes, you could have written something like:

static boolean isPattern(String givenPattern, String stringToMatch) {
    String regex = "^" + givenPattern.replace("*", ".*").replace("?", ".") + "$";

    return Pattern.compile(regex).matcher(stringToMatch).matches();
}

"^" is the start of the string
"$" is the end of the string
. is for "any character", exactly once
.* is for "any character", 0 or more times

Note: If you want to restrict * and ? to letters only, you can use [a-zA-Z] instead of ..

Answer 2

boolean isPattern(String givenPattern, String stringToMatch) {
    if (givenPattern.empty)
        return stringToMatch.isEmpty();
    char patternCh = givenPatter.charAt(0);
    boolean atEnd = stringToMatch.isEmpty();
    if (patternCh == '*') {
        return isPattenn(givenPattern.substring(1), stringToMatch)
            || (!atEnd && isPattern(givenPattern, stringToMatch.substring(1)));
    } else if (patternCh == '?') {
        return !atEnd && isPattern(givenPattern.substring(1), 
            stringToMatch.substring(1));
    }
    return !atEnd && patternCh == stringToMatch.charAt(0)
          && isPattern(givenPattern.substring(1), stringToNatch.subtring(1);
}

(Recursion being easiest to understand.)