Coderust: Hacking the Coding Interview/

...

/

Regular Expression Matching in String

Regular Expression Matching in String

Given a text and a pattern, evaluate the pattern to see if it matches the text by using regular expression matching.

We'll cover the following...

Statement

Given a text and a pattern, determine if the pattern matches the text completely or not at all by using regular expression matching. For simplicity, assume that the pattern may contain only two operators: . and *.

* operator in the pattern means that the character preceding * may not appear or may appear any number of times in the text. The . operator matches with any character in the text exactly once.

Example

Below is an example of a text and its matching and non-matching patterns:

g d Text aabbbbbcdda Matching Patterns Non-Matching Patterns a*bb*cdda aabbbbbcdd a*bb*.dda a*b*c*da aab*e*cd*a a*b*c*d*a* .*b*c*d*a* aabbbbbcdda

Sample input

Text = fabbbc
Pattern = .ab*c

Expected output

true

Try it yourself #

#include <iostream>
#include <string>
using namespace std;
bool RegxMatch(const string& text, const string& pattern) {
	//TODO: Write - Your - Code
	return false;
}

Solution 1

If there are no operators in the pattern, then regex matching is a simple string comparison. Handling the . operator is also very easy as it can match with any character in the text. However, handling the * operator is not that simple. To handle *, let’s look at the below example.

Suppose the given text is fabbbc, and the given pattern is .ab*c. We start matching from the first character of both the text and the pattern. The first character of the pattern is . and the first character of the text is f. Since . matches with any character, they match. Now, we match the remaining text and the remaining pattern recursively , that is, we match ab*c and abbbc.

g d Text f abbbc Pattern . ab*c

For the remaining text and remaining pattern, the first character of the pattern is a, and the first character of text is also a. They both match, so we again match the ...