Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created December 21, 2017 20:58
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/f455089d87ce8d84edbc102697dd625c to your computer and use it in GitHub Desktop.
Save jianminchen/f455089d87ce8d84edbc102697dd625c to your computer and use it in GitHub Desktop.
Leetcode 10 - code review, and then write in C# code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LeetcodeDynamicProgramming_Practice
{
/// <summary>
/// code review on Dec. 21, 2017
/// Study Java code written by the blog author:
/// https://segmentfault.com/a/1190000003904286
/// Leetcode 10: regular expression matching
/// </summary>
class Program
{
static void Main(string[] args)
{
RunTestcase2();
}
public static void RunTestcase1()
{
var result = isMatch("aaa", "aaaa");
}
public static void RunTestcase2()
{
var result = isMatch("aaa", "ab*a*c*a");
}
/// <summary>
/// </summary>
/// <param name="search"></param>
/// <param name="pattern"></param>
/// <returns></returns>
public static bool isMatch(String search, String pattern)
{
var length = search.Length;
var pLength = pattern.Length;
var match = new bool[length + 1];
match[length] = true;
int pIndex = pLength -1;
while(pIndex >= 0)
{
if (pattern[pIndex] == '*')
{
var previousPattern = pattern[pIndex - 1];
// if it is *,match from backward iteration
for (int matchIndex = length - 1; matchIndex >= 0; matchIndex--)
{
match[matchIndex] = match[matchIndex] || (match[matchIndex + 1] && (previousPattern == '.' ||
previousPattern == search[matchIndex]));
}
//extra decrement one, because * needs extra char to work together. .* or a* etc.
pIndex -= 2;
}
else
{
var currentPattern = pattern[pIndex];
// foreward iteration
for (int searchIndex = 0; searchIndex < length; searchIndex++)
{
match[searchIndex] = match[searchIndex + 1] && (currentPattern == '.' || currentPattern == search[searchIndex]);
}
// 只要试过了pattern中最后一个字符,就要把match[s.length()]置为false
match[length] = false;
pIndex -= 1;
}
}
return match[0];
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment