Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created January 14, 2018 05:19
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/6cc3764d6cb9627d968ecfdf681178e7 to your computer and use it in GitHub Desktop.
Save jianminchen/6cc3764d6cb9627d968ecfdf681178e7 to your computer and use it in GitHub Desktop.
Regular expression match - coached by the peer, apply 0 time, apply 1 time, apply 2 times,
using System;
class Solution
{
public static bool IsMatch(string text, string pattern) // "aa", "a"
{
if(pattern == null || pattern.Length == 0) // false
{
return text == null || text.Length == 0;
}
if(text == null)
{
return false;
}
int length1 = text.Length + 1;
int length2 = pattern.Length + 1;
int[, ] dp = new int[length1, length2];
for(int row = 0; row < length1; row++)
{
// base case -
var isFirstRow = row == 0;
for(int col = 0; col < length2; col++)
{
if(isFirstRow)
{
dp[0, col] = col > 0? 0 : 1;
}
var isFirstCol = col == 0;
if(isFirstCol)
{
dp[row, 0] = isFirstRow? 1 : 0;
}
// handle case after base case
if(isFirstRow || isFirstCol)
{
continue;
}
var charText = text[row - 1];
var charPattern = pattern[col - 1];
var isDot = charPattern == '.';
var isStar = charPattern == '*';
// match one char
if(!isStar)
{
if(dp[row - 1, col - 1] == 1 && (isDot || charText == charPattern))
{
dp[row, col] = 1;
}
}
else
{
// isStar = True, apply zero time, one time or more than one time
// zero time one time dot char char comparison more than one time
if(dp[row, col - 2] == 1 || dp[row, col -1] == 1 || ((pattern[col -2] == '.' || charText == charPattern) && dp[row - 1, col] == 1))
{
dp[row, col] = 1;
}
/*
0 - "", a 1, * 2
a* - pattern len = 2, col = 1
b - text
*/
}
}
}
return dp[length1 - 1, length2 - 1] == 1;
}
static void Main(string[] args)
{
}
}
/*
aa, a -> false
a - a , a text cannot match any thing, - false text is not empty, pattern is empty
aa, aa -> a - a, a - a
abc -> a.c , a -a, b -. c - c
abbb - ab* -> abbb - ab* -> a - a, bbb - b*, b repeats 3 times
acd - ab*c -> a - a , b* match 0, cd match c -> false
match, cd match bc -> false
false
text length1
pattern length2
abb abb*
"" "a" "ab" "abb" "abb*"
------------------------------------
"" T F F F F
"a" F
"ab" F - ?
"abb" F ?
"abb" with "abb"
"abb" with "ab"
"ab" with "abb"
"ab" with "ab"
check . || (search[i] == pattern[j])
has *, b* or .*
check if b* apply 0 time or 1 time or more than 1 times
matrix(i, j - 2) || matrix(i - 1, j - 2) || matrix(i - 1, j)
b* -> "", b, bb, bbb
.* -> "", b, bb, bbb
Pattern ----
Text ----
apply 0 time - matrix(i, j - 2) | ""
apply 1 time - b* - check search[i] == pattern[j -1] && matrix(i - 1, j -2) -> optimized to this expression, take away one star matrix(i, j-1) -
.* matrix(i -1, j - 2) | b
apply more than 1 time
(pattern[j -1] == '.' || search[i] == pattern[j -1]) && matrix(i - 1 , j)
*/
/*
// aab, c*a*b
// ab, .b
// aaa, ab*a
*/
@jianminchen
Copy link
Author

The C# code does not pass the test case "" matching "b*", the peer coached me b* pattern - how to apply one time, just skip last pattern char; in total, apply zero time, one time or more than one time.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment