Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/b587ac3af346f3ba28ae8fbae7324ea0 to your computer and use it in GitHub Desktop.
Save jianminchen/b587ac3af346f3ba28ae8fbae7324ea0 to your computer and use it in GitHub Desktop.
Leetcode 10 regular expression - mock interview
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
*/
// a a
// ab ab
// a .
// a b* - false
// b b* - true - one time
// b b*b - zero time
// bb b* - more than one time
// "" b*
// "" b*a*
// a "" - return false
public static bool RunRegularExpressionMatching(string text, string pattern, int tIndex, int pIndex) // 0, 0
{
// base case a, a*
if(text == null || pattern == null) // ?
return false;
var tLength = text.Length;
var pLength = pattern.Length;
if(pLength == pIndex) // pattern ""
{
return tLength == tIndex; // "", "a" -> false - line 30
}
if(tIndex == tLength) // "", "a*b*" -> true, **,
{ // * pattern
return (pattern[pIndex] != '*' && pLength > pIndex && pattern[pIndex + 1] == '*') && RunRegularExpressionMatching(text, pattern, tIndex, pIndex + 2);
}
// recurrence step
var tChar = text[tIndex]; // tIndex < tLength(true, line 45)
var pChar = pattern[pIndex]; // pIndex < pLength (true, line 40)
// * - star not last char in the range
var starPattern = (pIndex + 1) < pLength && pattern[pIndex + 1] == '*';
if(!starPattern)
{
// one char comparison and then recursive call
if(! (pChar == '.' || tChar == pChar) )
return false;
return RunRegularExpressionMatching(text, pattern, tIndex + 1, pIndex + 1);
}
else
{ // one time first, more than one time, zero time abc a*b*c*......b
return RunRegularExpressionMatching(text, pattern, tIndex + 1, pIndex + 2) || // one time
RunRegularExpressionMatching(text, pattern, tIndex + 1, pIndex) || // more than one time
RunRegularExpressionMatching(text, pattern, tIndex, pIndex + 2); // zero time
}
}
/*
leetcode 10: regular expression matching
regular expression
ab ab*
abb ab*b
| |
I saw swift -> recursive -> recursive on pattern/ text string
"" match b*a*c* -> recursive on pattern string
| | b* -> 0 time, 1 time, more than one time,
b*
. any char -> one char matching
abb
ab*b
-> true
a a -> true -> index1+1, index2 + 1
b, b* -> return 0 time, 1 time, more than one time
index2 +2 one char comparison true one char comparison b vs b
index1 + 1 index1 + 1
index2 + 2 index2
base case:
pattern string emtpy, text string not empty -> false
text string empty, a*.. -> ("", substring(2,))
not b* style, return false
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment