Leet 10 – Regular Expression Matching

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

My Solution:
First I can see that I need to case out ‘*’ and ‘.’,
otherwise I need to follow orderly with indexes the input pattern letters and see that they match;

1. In the case of . I will check if there exists any single letter in the string and advance the relevant index positions .

2. For the case * I will check if there are 0 occurrences of the letter before.
2.a. if there are many cases of the letter before or if it was ‘.’ I will loop while it repeats.

So I can have some sort of loop or recursive function to check out the cases and update the relevant positions.

class Solution {
public:

bool isMatch(string s, string p) {
    if (p.empty()) return s.empty();
    if (p[1] != '*') { // case 1
        if(s[0] == p[0] || (p[0] == '.' && s[0] != '\0')) {
                return isMatch(s.substr(1), p.substr(1));
        } else return false;
        
    } else {  // case 2 - first check if there are 0 occurrences of the letter before that means ignore the 2 case completely 
        if (isMatch(s, p.substr(2))) {
           return true;
        }

        int index = 0; // case 2.a.
        while (index < s.size() && (s[index] == p[0] || p[0] == '.')) {  // if there exists any char that repeats continue while string is not over
            if (isMatch(s.substr(++index), p.substr(2))) { // mean time check as if star finished and did not repeat for early break.
               return true;
            }
        }
       
        return false;
      }
 }
};

Complexity Analysis

• Time complexity : The worst time case in my solution is calling the IsMatch function for every letter and because all of the pattern has to match we need to traverse all the pattern letters as well, so defining n as length of s, m as length of p,  making it O(n+m).
• Space complexity : O(1) for the index space variable, and the same O(n+m) because for each substring copy of string when the IsMatch function is called.