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 lettersa-z
.p
could be empty and contains only lowercase lettersa-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.