Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created November 8, 2017 22:04
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/8460319a326e82b9da8dc0a059eed688 to your computer and use it in GitHub Desktop.
Save jianminchen/8460319a326e82b9da8dc0a059eed688 to your computer and use it in GitHub Desktop.
Leetcode 10 - timeout issues - how to analysis the issue?
using System;
class Solution
{
public static bool IsMatch(string text, string pattern) //"abc" "a.c"
{
// base case
if(text == null || pattern == null)
{
return false;
}
if(pattern.Length == 0)
{
return text.Length == 0; // true, "a", ""
}
return isMatchHelper(text, pattern, 0, 0);
}
// "abbb", 1, "bbb" , "ab*", 0, "bbb" with "ab*"
private static bool isMatchHelper(string text, string pattern, int textIndex, int patternIndex) // abbb, ab*
{
var lengthText = text.Length;
var lengthPattern = pattern.Length;
// base case
if (patternIndex == lengthPattern)
{
return lengthText == textIndex;
}
var template = pattern[patternIndex]; //'a'
var isContainingStar = template != '*' && patternIndex < lengthPattern - 1 && pattern[patternIndex + 1] == '*'; // standalone "*"
// base case - text string is empty but pattern string not emtpy
if ((lengthText == 0 || lengthText == textIndex) && isContainingStar)
{
return isMatchHelper(text, pattern, textIndex, patternIndex + 2);
}
if (lengthText == textIndex)
{
return false;
}
// pattenrIndex < lengthPattern
// single char match
var visit = text[textIndex]; // out-of-index range // 'a'
if (!isContainingStar)
{
var comparisonEqual = visit == template || template == '.';
if (!comparisonEqual)
{
return false;
}
return isMatchHelper(text, pattern, textIndex + 1, patternIndex + 1);
}
// assuming that containing *
// return at least 2 branch, pattern a*, or .*
// match 0 time, match 1 time or more than 1 time
if (isMatchHelper(text, pattern, textIndex, patternIndex + 2)) // abbb, ab*
{
return true;
}
else if (visit == template || template == '.') // match one time
{
var matchOneTime = isMatchHelper(text, pattern, textIndex + 1, patternIndex + 2);
if (matchOneTime)
{
return true;
}
return isMatchHelper(text, pattern, textIndex + 1, patternIndex); // text = bbb, pattern b*b; text = bb
} // bbb b -> false
// b == b || b == '.' one time , bb match b -> false
// bb match b*b -> it will
return false;
}
static void Main(string[] args)
{
Console.WriteLine(IsMatch("bbbba",".*a*a"));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment