Microsoft Interview Question
Software Engineer / DevelopersTeam: yammer
Country: United States
My simple recursive solution:
// fwd decls
bool match_dot(const char *r, const char *s);
bool match_star(char c, const char *r, const char *s);
bool match(const char *r, const char *s)
{
if (*r == 0)
{
return *s == 0;
}
if (*r == '.')
{
return match_dot(r + 1, s);
}
if (*(r+1) == '*')
{
return match_star(*r, r + 2, s);
}
if (*r == *s)
{
return match(r + 1, s + 1);
}
else
{
return false;
}
}
bool match_dot(const char *r, const char *s)
{
if (*r == 0) return true;
while (*s != 0)
{
if (match(r, s)) return true;
s++;
}
return false;
}
bool match_star(char c, const char *r, const char *s)
{
if (*s == c)
{
if (match_star(c, r, s + 1)) return true;
}
return match(r, s);
}
public class PatternMatcherRegex {
public static boolean match(String regX, String candidate) {
//If regex is empty, the pattern doesnt match
if(regX.isEmpty())
return false;
if(regX.charAt(0) == '*') {
if(regX.length() == 1) {
/**
* The last regex character is *,
* which matches everything
*/
return true;
}
else {
return matchStar(regX.substring(1), candidate);
}
}
else if(candidate.isEmpty()) {
//Candidate is empty but the pattern is not
return false;
}
else if(regX.charAt(0) == '.' || regX.charAt(0) == candidate.charAt(0)) {
//Last regex matches last character
if(regX.length() == 1 && candidate.length() == 1)
return true;
else {
return match(regX.substring(1), candidate.substring(1));
}
}
else
return false;
}
public static boolean matchStar(String regX, String candidate) {
for(int i = 0; i < candidate.length(); i++) {
if(match(regX, candidate.substring(i)))
return true;
}
return false;
}
public static void main(String[] args) {
System.out.println(match("a.b", "accb"));
}
}
- jvermette October 22, 2013