# Problem Statement
Given a text and a pattern, determine if the pattern matches with 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. Operator ‘.’ matches with any character in the text exactly once.

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



<br>

# Hint
* Recursion

<br>

# Try it yourself

bool regx_match(const string& text, const string& pattern) {
  //TODO: Write - Your - Code
  return false;
}

#include <string>
#include <iostream>
#include <regex>
#include <assert.h>
using namespace std;

class RegxMatch{
  static boolean regxMatch(String text, String pattern) {
    //TODO: Write - Your - Code
    return false;
  }
}

Java

def regx_match(text, pattern):
  #TODO: Write - Your - Code
  return False

Python

let regxMatch = function(text, pattern) {
  //TODO: Write - Your - Code
  return false;
};

JavaScript

def regx_match(text, pattern)
  #TODO: Write - Your - Code
  return false
end

Ruby

bool regx_match_rec(const string & text,
  const string & pattern,
    int i, int j) {

  if (pattern.length() == j) {
    if (text.length() == i) {
      return true;
    } else {
      return false;
    }
  }

  if (j < pattern.length() - 1 && pattern[j + 1] == '*') {
    for (int k = i; k <= text.length(); ++k) {
      if (regx_match_rec(text, pattern, k, j + 2)) {
        return true;
      }

      if (pattern[j] != '.' && text[k] != pattern[j]) {
        return false;
      }
    }
  } else if (i < text.length() && j < pattern.length() &&
    (pattern[j] == '.' || pattern[j] == text[i])) {
    return regx_match_rec(text, pattern, i + 1, j + 1);
  }

  return false;
}

bool regx_match(const string & text, const string & pattern) {
  return regx_match_rec(text, pattern, 0, 0);
}

int main() {
  string text = "fabbbc";
  string pattern = ".ab*c";
  bool match1 = regx_match(text, pattern);
  cout << text << " " << pattern;
  cout << (match1 ? " match" : " did not match.");

  smatch m;
  regex e(pattern);
  bool expected = regex_match(text, m, e);
  assert(match1 == expected);

  cout << endl;
}

class RegxMatch {
  public static boolean regxMatchRec(String text, String pattern, int i, int j) {
    if (text.length() == i && pattern.length() == j) {
      return true;
    }

    if (j<pattern.length() - 1 && pattern.charAt(j + 1) == '*') {
      for (int k = i; k<= text.length(); ++k) {
        if (regxMatchRec(text, pattern, k, j + 2)) {
          return true;
        }

        if (k >= text.length()) {
          return false;
        }

        if (pattern.charAt(j) != '.' && text.charAt(k) != pattern.charAt(j)) {
          return false;
        }
      }
    } else if (i<text.length() && j<pattern.length() &&
      (pattern.charAt(j) == '.' || pattern.charAt(j) == text.charAt(i))) {
      return regxMatchRec(text, pattern, i + 1, j + 1);
    }

    return false;
  }

  public static boolean regxMatch(String text, String pattern) {
    return regxMatchRec(text, pattern, 0, 0);
  }

  public static void main(String[] args) {
    String s = "fabbbc";
    String p = ".ab*c";
    boolean output2 = regxMatch(s, p);

    Pattern pattern = Pattern.compile(p);
    Matcher matcher = pattern.matcher(s);
    
    if (output2) {
			System.out.print(s + " " + p + " match");
		} else {
			System.out.print(s + " " + p + " did not match.");
		}
	}
}

def regx_match_rec(text, pattern, i, j):
  if len(text) == i and len(pattern) == j:
    return True

  if j < len(pattern) - 1 and pattern[j + 1] == '*':
    for k in range(i, len(text) + 1):
      if regx_match_rec(text, pattern, k, j + 2):
        return True

      if k >= len(text):
        return False

      if pattern[j] != '.' and text[k] != pattern[j]:
        return False
  elif (i < len(text) and
          j < len(pattern) and
          (pattern[j] == '.' or pattern[j] == text[i])):
    return regx_match_rec(text, pattern, i + 1, j + 1)

  return False

def regx_match(text, pattern):
  return regx_match_rec(text, pattern, 0, 0)

s = "fabbbc"
p = ".ab*c"
output = regx_match(s, p)

pt = re.compile(p)

output3 = False
m = pt.match(s)
if m and m.end() == len(s):
  output3 = True

if output == True:    
  print(s, p, end =" ")
  print("match")
  
else:
  print(s, p, end = " ")
  print("did not match.")

assert output == output3  

def regx_match_rec(text, pattern, i, j)
  if (text.length == i && pattern.length == j)
    return true
  end

  if (j < pattern.length - 1 && pattern[j + 1] == '*')
    for k in i .. text.length
      if (regx_match_rec(text, pattern, k, j + 2))
        return true
      end

      if (k >= text.length)
        return false
      end

      if (pattern[j] != '.' && text[k] != pattern[j])
        return false
      end
    end
  elsif (i < text.length && j < pattern.length && (pattern[j] == '.' || pattern[j] == text[i]))
    return regx_match_rec(text, pattern, i + 1, j + 1)
  end

  return false
end

def regx_match(text, pattern)
  return regx_match_rec(text, pattern, 0, 0)
end

s = "fabbbc"
p = ".ab*c"
output = regx_match(s, p)
pt = Regexp.new(p)
output3 = false
m = pt.match(s)
if m and m.end(0) == s.length
  output3 = true
end

if (output == true)
  print s.to_s + " " + p.to_s + " match"
else
  print s.to_s + " " + p.to_s + " did not match."
end

# Solution Explanation
## Runtime complexity 
The runtime complexity of this solution is exponential, $O(2^{n})$

## Memory complexity
The memory complexity of this solution is exponential, $O(2^{n})$

<br>

## Solution Breakdown
We’ll compare the text and pattern character by character and recursively compare the remaining text and remaining pattern. In this solution, we use indices of text and pattern instead of creating sub-strings and pass the same strings in the recursive calls.

The worst-case time complexity for this solution is still exponential, but we do save memory and time that was previously being spent on copying strings. For example, if text is aaa and pattern is a*a*a*. First, we’ll match a*a* with aaa, aa, a, and an empty string. Then we’ll match a* with aaa, aa, a, and an empty string.

> Practice problems like this and many more by checking out our [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) course!

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

Regular Expression

Problem Statement

Hint

Try it yourself

Solution

Solution Explanation

Runtime complexity

Memory complexity

Solution Breakdown