2
\$\begingroup\$

The interview question is:

Write a function isMatch (without using java.util.Regex) that takes two strings as arguments:

  • s (a string to match), and
  • p (a regular expression pattern).

It should return a Boolean denoting whether s matches p.

p can be composed of alphabetic characters and '*' (denoting that the previous character matches 0 or more times).

This is the code I have written:

    private boolean isNextCharStarred(String s) {
         return s.length() >= 2 && s.charAt(1) == '*';
     }

     private boolean recIsMatch(String s, String p, boolean hasPatternBeenEaten) {
         if (p.length() == 0) {
             return true;
         }
         if (s.length() == 0) {
             if (isNextCharStarred(p)) {
                 return recIsMatch(s, p.substring(2), true);
             }
             return p.length() == 0;
         }
         if (isNextCharStarred(p)) {
             if (s.charAt(0) != p.charAt(0)) {
                 return recIsMatch(s, p.substring(2), true);
             }
             return recIsMatch(s.substring(1), p, hasPatternBeenEaten) 
|| recIsMatch(s, p.substring(2), true);
         }
         if (s.charAt(0) == p.charAt(0)) {
             return recIsMatch(s.substring(1), p.substring(1), true);
         }
         if (hasPatternBeenEaten) {
             return false;
         }
         return recIsMatch(s.substring(1), p, hasPatternBeenEaten);
     }

     public boolean isMatch(String s, String p) {
         return recIsMatch(s, p, false);
     }

Are there any bugs? How could it be improved?

\$\endgroup\$
1
\$\begingroup\$

Empty pattern should only match empty text

isMatch("aa", "a") returns true, when it should be false. The problem is with this condition:

 if (p.length() == 0) {
     return true;
 }

An empty pattern should match only an empty text:

 if (p.isEmpty()) {
     return s.isEmpty();
 }

Notice that I replaced s.length() == 0 with s.isEmpty(). This is a more natural way to check if a string is empty.

Use better variable names

Instead of s and p it would be more natural to call them text and pattern.

The function isNextCharStarred is always used on the pattern, but its parameter is called s, which is the same name as the variable used for text in the other function. Even p would have been less confusing. pattern would be nice and natural.

Eliminate hasPatternBeenEaten

The parameter hasPatternBeenEaten looked a bit suspicious to me. Let's take a closer look.

The value of the variable is only read in one place in the code. Let's look at the piece code just before that:

 if (isNextCharStarred(p)) {
     // will always return from this block
 }
 if (s.charAt(0) == p.charAt(0)) {
     return ...
 }
 if (hasPatternBeenEaten) {
     return false;
 }

That is:

  • If the pattern starts with X* (where X is any letter), the first if block will return.
  • If the pattern doesn't start with X*, and the first characters match, the second if block will return.
  • If the pattern doesn't start with X*, and the first characters don't match, then we need not look further: the pattern doesn't match, we can return false.

Therefore, the hasPatternBeenEaten is unnecessary, and can be safely eliminated.

Simplify

With the above changes, the code will look more like this:

  private boolean isMatch(String text, String pattern) {
    if (pattern.isEmpty()) {
      return text.isEmpty();
    }

    if (text.isEmpty()) {
      if (isNextCharStarred(pattern)) {
        return isMatch(text, pattern.substring(2));
      }
      return pattern.isEmpty();
    }

    if (isNextCharStarred(pattern)) {
      if (text.charAt(0) != pattern.charAt(0)) {
        return isMatch(text, pattern.substring(2));
      }
      return isMatch(text.substring(1), pattern)
        || isMatch(text, pattern.substring(2));
    }

    if (text.charAt(0) == pattern.charAt(0)) {
      return isMatch(text.substring(1), pattern.substring(1));
    }

    return false;
  }

This can probably be written simpler, by rearranging the conditions and extracting common patterns.

First of all the second pattern.isEmpty() condition is redundant, because at that point we already know that pattern is not empty, due to the very first condition in the method.

Next, we can extract the common condition text.charAt(0) == pattern.charAt(0) to a variable firstMatch, and flatten the if conditions to direct return statements, like this:

if (pattern.isEmpty()) {
  return text.isEmpty();
}

if (text.isEmpty()) {
  return isNextCharStarred(pattern) && isMatch(text, pattern.substring(2));
}

boolean firstMatch = text.charAt(0) == pattern.charAt(0);

if (isNextCharStarred(pattern)) {
  return firstMatch && isMatch(text.substring(1), pattern)
    || isMatch(text, pattern.substring(2));
}

return firstMatch && isMatch(text.substring(1), pattern.substring(1));

Lastly, we can generalize firstMatch to include the case of empty text, which will make the second if redundant:

if (pattern.isEmpty()) {
  return text.isEmpty();
}

boolean firstMatch = !text.isEmpty() && text.charAt(0) == pattern.charAt(0);

if (isNextCharStarred(pattern)) {
  return firstMatch && isMatch(text.substring(1), pattern)
    || isMatch(text, pattern.substring(2));
}

return firstMatch && isMatch(text.substring(1), pattern.substring(1));
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.