10. Regular Expression Matching
1. Description
Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’ where:
- ‘.’ Matches any single character.
- ‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
2. Example
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 = “cab”
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 = “misisp*.”
Output: false
3. Constraints
- 0 <= s.length <= 20
- 0 <= p.length <= 30
- s contains only lowercase English letters.
- p contains only lowercase English letters, ‘.’, and ‘*’.
- It is guaranteed for each appearance of the character ‘*’, there will be a previous valid character to match.
4. Solutions
My Accepted Solution
recursion, and I don’t know how to calculate its complexity
The key is how to match ‘*’, it could match no letter, or one letter, or two letters, or more, especially with ‘.’
But we can’t give that much ‘if’ branch, actually, it only has two cases:
1 ‘*’ match no letters, we just pass it and its previous letter
2 ‘*’ match a leeter, if current two letters match, we could let ‘*’ try to match more letters
So, it will have some(or zero) case 2, then at some point, it face the case 1 and pass ‘*’ to judge the next letter
It is easier to pass a string to the recursion function, but it will take more time, so, it will be better to pass a reference and an index
At the end, it is slow as well, it could only beats 23.12% commits with C++
class Solution
{
public:
// bool isMatch(string s, string p)
bool isMatch(string str, string pattern)
{
if(pattern.empty()) return str.empty();
bool firstLetterMatch = (!str.empty() && (str[0] == pattern[0] || pattern[0] == '.'));
if(pattern.size() >= 2 && pattern[1] == '*')
{
return isMatch(str, pattern.substr(2))
|| firstLetterMatch && isMatch(str.substr(1), pattern)
;
}
else
{
return firstLetterMatch && isMatch(str.substr(1), pattern.substr(1));
}
}
};
class Solution
{
private:
bool isMatch(string &i_str, int strIndex, string &i_pattern, int patternIndex)
{
if(patternIndex == i_pattern.size()) return strIndex == i_str.size();
bool firstLetterMatch = (strIndex < i_str.size()
&& (i_str[strIndex] == i_pattern[patternIndex] || i_pattern[patternIndex] == '.'));
if(patternIndex + 1 < i_pattern.size() && i_pattern[patternIndex + 1] == '*')
{
return isMatch(i_str, strIndex, i_pattern, patternIndex + 2)
|| firstLetterMatch && isMatch(i_str, strIndex + 1, i_pattern, patternIndex)
;
}
else
{
return firstLetterMatch && isMatch(i_str, strIndex + 1, i_pattern, patternIndex + 1);
}
}
public:
// bool isMatch(string s, string p)
bool isMatch(string &i_str, string &i_pattern)
{
return isMatch(i_str, 0, i_pattern, 0);
}
};
4.1 Dynamic Programming
n is the product of i_str.size() * i_pattern.size() Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// bool isMatch(string s, string p)
bool isMatch(string &i_str, string &i_pattern)
{
const int strLen = i_str.size(), patLen = i_pattern.size();
vector<vector<bool>> match(strLen + 1, vector<bool>(patLen + 1, false));
match[0][0] = true;
// pass the pattern like "a*b*c*d*..."
// they have lots of letters, but actually, most of them could be passed
for(int i = 1; i < patLen; i++) // i is the index of i_pattern
{
if(i_pattern[i] == '*' && match[0][i - 1] == true)
match[0][i+1] = true;
}
for(int i = 0; i < strLen; i++) // i is the index of i_str
{
for(int j = 0; j < patLen; j++) // j is the index of i_pattern
{
if(i_str[i] == i_pattern[j] || i_pattern[j] == '.')
{
match[i+1][j+1] = match[i][j];
}
else if(i_pattern[j] == '*' && j >= 1)
{
if(i_str[i] != i_pattern[j-1] && i_pattern[j-1] != '.')
match[i+1][j+1] = match[i+1][j-1];
else
match[i+1][j+1] = match[i+1][j-1] || match[i+1][j] || match[i][j+1]; // '*' 0, 1, more times
}
else
{
match[i+1][j+1] = false;
}
}
}
return match[strLen][patLen];
}
};