My Concise 20 line C# Solution using Recursion


  • 2

    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;
        }
    }

  • 0
    This post is deleted!

  • 0

    Continue to add some discussion about memoization. Your implementation is great to avoid memoization.

    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;
    using System.Threading.Tasks;
    
    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;
            }
        }
    }

Log in to reply
 

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