Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created December 26, 2017 22:52
Show Gist options
  • Save jianminchen/b40246c628081e799afeb7d8b20fdd31 to your computer and use it in GitHub Desktop.
Save jianminchen/b40246c628081e799afeb7d8b20fdd31 to your computer and use it in GitHub Desktop.
Leetcode 10 - regular expression match - fix bug on line 26, 43
using System;
class Solution
{
public static bool IsMatch(string text, string pattern)
{
return IsMatch(text, pattern, 0, 0);
}
/// <summary>
/// The code was written when I was an interviewer on Dec. 26, 2017
/// </summary>
/// <param name="text"></param>
/// <param name="pattern"></param>
/// <param name="tIndex"></param>
/// <param name="pIndex"></param>
/// <returns></returns>
public static bool IsMatch(string text, string pattern, int tIndex, int pIndex)
{
if (pIndex >= pattern.Length && tIndex >= text.Length) // correct
return true;
if (pIndex >= pattern.Length) //"" match "a*", "a" match "" false
return false;
if (pattern[pIndex] == '.' && (pIndex == pattern.Length - 1 || pattern[pIndex + 1] != '*'))
return IsMatch(text, pattern, tIndex + 1, pIndex + 1); // correct
if (pIndex == pattern.Length - 1 || pattern[pIndex + 1] != '*')
{ // not including
if (text[tIndex] != pattern[pIndex]) // correct
return false;
return IsMatch(text, pattern, tIndex + 1, pIndex + 1);
}
// * missing *
// the cur char is followed by a '*'
// cur char in pattern is c
if (IsMatch(text, pattern, tIndex, pIndex + 2)) // char in pattern repeated 0 times
return true;
while (tIndex < text.Length && (text[tIndex] == pattern[pIndex] || pattern[pIndex] == '.'))
{
if (IsMatch(text, pattern, tIndex + 1, pIndex + 2)) // 1 times, text do not move forward, pattern move forward
return true;
tIndex++; // repeat more than 1 time
}
return false;
}
static void Main(string[] args)
{
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment