Question
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
Stats
| Frequency | 3 |
| Diffficulty | 5 |
| Adjusted Difficulty | 4 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
Very important to note: Do not use DP. Why? Because eg. “a*b” will be considered as 2 parts: “a*“ part and “b” part. Because star is considered to be bundled with previous char, it gives us difficulty in determine the size of the DP array. Of course, we still can do it, but I see nobody have provided a nice DP solution online. Let’s just forget about it for now.
The solution I’m giving in this post, is to trim String and compare.
We only need to consider 2 cases:
One, the next char is NOT a star sign. This requires simply char compare.
Two, the next char is a star sign, this will require some effort.
Solution
In case of one letter bundled with a star sign, we iterate thru all possible number of repetition of current char (from 0 until large), and check validation one by one.
A final important note, this question very much looks like DP, but NOT DP.
My code
My code.
public class Solution {
public boolean isMatch(String s, String p) {
// eg. s = "aab" p = "c*a*b"
return check(s, p, 0, 0);
}
private boolean check(String s, String p, int start1, int start2) {
int len1 = s.length();
int len2 = p.length();
if (start1 == len1 && start2 == len2) {
return true;
} else if (start2 == len2) {
// if p is used up, but still some letters left in s
return false;
}
// check if there is * after start2 in p
if (start2 == len2 - 1 || p.charAt(start2 + 1) != '*') {
// if there is no *
// match only 1 char
if (start1 == len1) {
// unable to match single char because s is fully used up
} else if (p.charAt(start2) != '.' && s.charAt(start1) != p.charAt(start2)) {
// if single char could not be matched
return false;
} else {
// if single letter matches
return check(s, p, start1 + 1, start2 + 1);
}
} else {
// if there is a * following start2
if (check(s, p, start1, start2 + 2)) {
// the letter in p represent 0 chars
return true;
} else {
// the letter in p represent 1 or more chars
// advance start1 until the end of s
while (start1 < len1) {
// check if the char matches
if (p.charAt(start2) != '.' && s.charAt(start1) != p.charAt(start2)) {
break;
}
if (check(s, p, start1 + 1, start2 + 2)) {
return true;
}
start1++;
}
}
}
return false;
}
}
A much shorter version from someone else making use of String.substring(). I refactored a bit.
public class Solution {
public boolean isMatch(String s, String p) {
// s is normal string, and p is regex string
if (p.length() == 0) {
return s.length() == 0;
} else if (p.length() < 2 || p.charAt(1) != '*') {
// if 2nd char in p is not '*', then match character
if (s.length() == 0) {
return false;
} else if (p.charAt(0) != '.' && s.charAt(0) != p.charAt(0)) {
return false;
} else {
return isMatch(s.substring(1), p.substring(1));
}
} else {
// if 2nd char in p is '*', then iterate all position repetitions
char repeatLetter = p.charAt(0);
for (int i = 0; i <= s.length(); i++) {
// i is the number of repetition of repeatLetter, start from 0
if (i > 0 && repeatLetter != s.charAt(i - 1)
&& repeatLetter != '.') {
break;
} else {
if (isMatch(s.substring(i), p.substring(2))) {
return true;
}
}
}
return false;
}
}
}