AI Features
Home
Courses
Coderust: Hacking the Coding Interview

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 ...