Created
July 7, 2017 00:09
-
-
Save jianminchen/606125e8b1ce05d1909d57fa733a2f6c to your computer and use it in GitHub Desktop.
Leetcode 10 - regular expression matching - pass online judge
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
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace StringMatchMocking | |
{ | |
class StringMatchMocking_May16Mocking | |
{ | |
static void Main(string[] args) | |
{ | |
bool result = IsMatch("a", "ab*"); | |
//bool result2 = isMatch("","a*"); | |
Console.WriteLine(result); | |
} | |
static bool IsMatch(string text, string pattern) | |
{ | |
// your code goes here | |
if ((text == null || text.Length == 0) && | |
(pattern == null || pattern.Length == 0)) | |
{ | |
return true; | |
} | |
if (pattern == null || pattern.Length == 0) | |
{ | |
return text.Length == 0; | |
} | |
// text is not null, pattern is not null, both not empty string | |
int left = 0; // text | |
int right = 0; // pattern | |
int length1 = text.Length; | |
int length2 = pattern.Length; | |
while (left < length1 && right < length2) | |
{ | |
var leftChar = text[left]; | |
var rightChar = pattern[right]; | |
//if(!isSpecailChar(rightChar) && | |
bool charNotEqual = leftChar != rightChar && rightChar != '.'; | |
bool charEqual = leftChar == rightChar || rightChar == '.'; | |
bool isZeroOrMore = isZeroOrMoreSequenceChar(right, pattern); | |
if (!isZeroOrMore) | |
{ | |
if (charNotEqual) | |
{ | |
return false; | |
} | |
else | |
{ | |
left++; | |
right++; | |
} | |
} | |
else | |
{ | |
// skip multiple left pointer bbbb | |
if (charEqual) | |
{ | |
if (text[left] == pattern[right] || pattern[right] == '.') | |
{ | |
// there are two choices - one is to increment left, | |
// another one is to increment right point | |
if(IsMatch(text.Substring(left), pattern.Substring(right + 2))) | |
{ | |
return true; | |
} | |
left++; | |
} | |
} | |
else | |
{ | |
right += 2; // b* | |
} | |
} | |
} | |
//edge case | |
if (left < length1 && right >= length2) | |
{ | |
return false; | |
} | |
if (right < length2) | |
{ | |
if (isZeroOrMoreSequenceChar(right, pattern)) | |
{ | |
return IsMatch("",pattern.Substring(right + 2)); | |
} | |
else | |
{ | |
return false; | |
} | |
} | |
return true; | |
} | |
private static bool isSpecialChar(char c) | |
{ | |
return c == '.' || c == '*'; | |
} | |
// b* pattern, b is any char, not special | |
private static bool isZeroOrMoreSequenceChar(int right, string pattern) | |
{ | |
var current = pattern[right]; | |
int length = pattern.Length; | |
return current != '*' && right < (length - 1) | |
&& pattern[right + 1] == '*'; | |
} | |
} | |
} | |
// . - one char | |
// * represent multiple symbol, b*, any number of b, | |
// including empty string, one more b, b, bb, bbb, | |
// text, pattern | |
// is matching or not | |
// aa, pattern a | |
// linear scan the string | |
// linear scan | |
// a - one case - not following by * | |
// b* - pattern, current char = b, if it is not, does not match, return false | |
// continuous more b -> while loop -> continuous scan until the pattern ends | |
// . - text current pointer scan to next one, if there is no char, then return false | |
// O(n) time complexity , n - string, m - pattern O(n+m) -> O(math.min(n,m)) | |
// space complexity -> two variable marks linear scan - > O(1) | |
// *, backward checking, *, | |
// edge case: | |
// 1. aa, a, -> false, second a cannot match anything, return false | |
// 2. aa, aa -> true | |
// 3. abc, a.c, -> true | |
// 4. abbb, ab*, bbb | |
// 4B. a, ab*, left text, right b*, but b* can be, matching | |
// 5 acd, ab*c., -> a, c b*, keep left pointer same, pattern moves to next c c, d compare to . -> c vs b*, c !=b, => c vs c | |
// Text: "" pattern : a*b* | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment