Created
March 14, 2018 02:58
-
-
Save jianminchen/b587ac3af346f3ba28ae8fbae7324ea0 to your computer and use it in GitHub Desktop.
Leetcode 10 regular expression - mock interview
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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