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));
