Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created November 10, 2017 01:34
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save jianminchen/94e96364362bd89eb1d58999b832a0e4 to your computer and use it in GitHub Desktop.
Leetcode 10 - pass online judge - Nov. 9, need to remove redundant code, "matching one time at least" branch precedes "match zero time" to avoid timeout.
using System;
class Solution
{
public 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);
}
var matchingFirstChar = visit == template || template == '.';
return ( matchingFirstChar && isMatchHelper(text, pattern, textIndex + 1, patternIndex)) || // match 1 time at least
isMatchHelper(text, pattern, textIndex, patternIndex + 2); // match 0 time
}
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