Facebook

www.facebook.com

Interview Question

Software Engineer Interview

bool regular_expression_match(char* pattern, char* string

  ) and pattern can contain kleene star.
Answer

Interview Answer

2 Answers

0

Do you mean pattern can only normal characters or star? Will other special characters be included, e.g. '?', '+', '{}', '[]', etc.?

Can you be more specific? on Mar 30, 2013
0

bool rep(char* pattern, char* string)
{
    if ((pattern[0] == 0) && (string[0] == 0)) return 1;
    if ((pattern[0] == 0) || (string[0] == 0)) return 0;
    if (pattern[1] == '*')
    {
        return (match(pattern, string) && (rep(pattern+2,string) || rep(pattern,string+1)));
    }
    else
    {
        return (match(pattern, string) && rep(pattern+1, string+1));
    }
}

bool match(char* pattern, char* string)
{
    if (*pattern == '.') return 1;
    return (*pattern == *string);
}

Rahul on May 3, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.