# My Concise 20 line C# Solution using Recursion

• Run-time is 160 ms. One thing to note is that several of the recursive calls are tail-recursive so compiler can optimize it.

``````public class Solution {
public bool IsMatch(string s, string p) {
return IsMatch(s,p,0,0);
}

bool IsMatch(string s, string p, int i, int j) {

//base case - reached end of pattern
if(j >= p.Length) {
return i >= s.Length && j >= p.Length;
}

if(j+1 < p.Length && p[j+1]=='*') { //peek ahead for *
while(i < s.Length && (s[i]==p[j] || p[j]=='.')) {
if(IsMatch(s,p,i,j+2)) return true;
i++;
}
return IsMatch(s,p,i,j+2);
} else if(i < s.Length && (s[i]==p[j] || p[j]=='.')) { //direct 1-to-1 match
return IsMatch(s,p,i+1,j+1);
}

return false;
}
}``````

• This post is deleted!

Here is my C# code I have to write a memo to avoid timeout issue, assuming that ' ' (space char) can be used as a delimiter to create a key.

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace StringMatching
{
/// <summary>
/// Leetcode 10: Regular Expression Matching
/// Pass all test cases using memo - July 2, 2017
/// </summary>
class Program
{
static void Main(string[] args)
{
var result = IsMatch("aa", "aa");
}

public static Dictionary<string, bool> memo = new Dictionary<string, bool>();

public static bool IsMatch(string text, string pattern)
{
if( text == null || pattern == null)
{
return false;
}

var key = text + " " + pattern;
if(memo.ContainsKey(key))
{
return memo[key];
}

if (pattern.Length == 1 && text.Length == 0)
{
return false; // "", "a"  return false
}

if (pattern.Length == 1 && text.Length == 1 && pattern[0] == '.')
{
return true; //  # "a" "." return true
}

// test case: "" "a*"
if (pattern.Length <= 1)
{
return text == pattern; // # "a" "a" pattern .
}

// test case: "","a*"

var test_pattern = pattern[0]; //#
bool isStar = pattern[1] == '*';
bool firstCharMatching = text.Length > 0 &&
(test_pattern == '.' || text[0] == test_pattern);
bool match = false;

if (isStar)
{
match = IsMatch(text, pattern.Substring(2)); // repeat 0 times

if (firstCharMatching)
{
// repeat at least one time
match |=  IsMatch(text.Substring(1), pattern);
}
}
else if (firstCharMatching)
{
match |= IsMatch(text.Substring(1), pattern.Substring(1));
}

memo[key] = match;

return match;
}
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.