2
\$\begingroup\$

Problem statement

Implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be: bool isMatch(const char *s, const char *p)

Some examples:

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Introduction of Algorithm

It is the hard level algorithm on Leetcode.com. And there are over 710 thousands submissions. I usually find that hard level algorithm is hard to learn and then I do not have experience before to learn and practice one hard level algorithm very well.

Because I have practiced the mock interview 5 rounds with same 30 algorithms since this March, and then I wrote this algorithm five times in mock interview, and also I interviewed peers over 5 times. This is the first hard level algorithm I have practiced over 10 times last 9 months and I found very challenging. I like to list a few practices at the end of questions as references, in case other people have interest to learn one hard level algorithm as I have done.

Every time there are new issues coming out after the mock interview, I have to figure out the issues. I just wrote code last Sunday and the code could not pass 5 out of 7 test cases. Today I reviewed the code and fixed the bug to pass test cases on mock interview platform and also on Leetcode 20 online judge.

Algorithm analysis

I like to write down some analysis I did at my last mock interview on Dec. 17, 2017. Usually I like to spend a few minutes to explain the algorithm using some test cases.

String "aa" does not match pattern string "a". String "aa" does match "aa". String "abc" does match "a.c" since '.' matches any char.

How to match string "abbb" with pattern "ab*"? Pattern string "b*" matches 0 or 1 and 1 more time. Recursive tree has two branches. if "b*" applies zero time, then "bbb" does not match "", return false. Apply one time at least, then next iteration is about "bb" matching "b*".

Time out test case if applying zero time first and then at least one time next. The following is a test case with detail explanation.

String "abcd" matches pattern string "a∗b∗c∗d∗". Concatenating string five times, string "abcdabcdabcdabcdabcdabcd" matches pattern string "a∗b∗c∗d∗a∗b∗c∗d∗a ∗b∗c∗d∗a∗b∗c∗d∗a ∗b∗c∗d∗". But it will time out if applying zero time first on "a*" and "b*" and "c*" and "d*", it will take time with complexity level 210 before applying one time match.

I chose to write a recursive solution using memoization in my last mock interview. Please help me to review C# implementation.

using System;
using System.Diagnostics;

class Solution
{
    public static bool IsMatch(string text, string pattern)
    {
        // base case: if pattern is empty, then it is ready to return the result. 
        if (pattern == null || pattern.Length == 0)
        {
            return text == null || text.Length == 0;
        }

        int lengthText = text.Length;
        int lengthPattern = pattern.Length;

        var memo = new int[lengthText + 1, lengthPattern + 1]; // 0 - not set, 1 - true, -1 - false

        return IsMatchHelper(text, pattern, memo, 0, 0);
    }

    /// <summary>
    /// recursive solution using memoization technique
    /// Recursive solution design is customized to avoid timeout. 
    /// Enforce the order to repeat one time first and then repeat 0 time next
    /// </summary>
    /// <param name="text"></param>
    /// <param name="pattern"></param>
    /// <param name="memo"></param>
    /// <param name="textIndex"></param>
    /// <param name="patternIndex"></param>
    /// <returns></returns>
    private static bool IsMatchHelper(string text, string pattern, int[,] memo, int textIndex, int patternIndex)
    {
        int lengthText = text.Length;
        int lengthPattern = pattern.Length;

        // base case 
        if (patternIndex == lengthPattern)
        {
            var textEmpty = textIndex == lengthText;
            memo[textIndex, patternIndex] = textEmpty ? 1 : -1;
            return textEmpty;
        }

        var firstCharIsDot = pattern[patternIndex] == '.';
        var isLastOne = patternIndex == lengthPattern - 1;
        var textIsEmpty = textIndex == lengthText;

        // base case II:        
        // apply to case: "" matches pattern strings "a*", "a*b*", ".*"
        if (textIsEmpty)
        {            
            var firstTwoWildMatch = patternIndex + 1 < lengthPattern && pattern[patternIndex + 1] == '*';
            return firstTwoWildMatch && IsMatchHelper(text, pattern, memo, textIndex, patternIndex + 2);
        }

        // Look up memo to avoid timeout
        if (memo[textIndex, patternIndex] != 0)
        {
            return memo[textIndex, patternIndex] == 1;
        }

        // compare one char with one pattern char
        if (isLastOne || pattern[patternIndex + 1] != '*')
        {
            // do one char comparison first
            var visit = text[textIndex];
            var patternChar = pattern[patternIndex];

            var isSameChar = isSame(visit, patternChar);

            if (isSameChar)
            {
                var nextIteration = IsMatchHelper(text, pattern, memo, textIndex + 1, patternIndex + 1);
                memo[textIndex, patternIndex] = nextIteration ? 1 : -1;
                return nextIteration;
            }
            else
            {
                memo[textIndex, patternIndex] = -1; 
                return false;
            }
        }
        else
        {
            var visit = text[textIndex];
            var patternChar = pattern[patternIndex];

            var firstRecursiveMatchOneTime = isSame(visit, patternChar) && 
                                             IsMatchHelper(text, pattern, memo, textIndex + 1, patternIndex);

            if (firstRecursiveMatchOneTime)
            {
                memo[textIndex, patternIndex] = 1;
                return true;
            }

            var secondRecurisveMatchZeroTime = IsMatchHelper(text, pattern, memo, textIndex, patternIndex + 2);
            if (secondRecurisveMatchZeroTime)
            {
                memo[textIndex, patternIndex] = 1;
                return true;
            }

            memo[textIndex, patternIndex] = -1;
            return false;
        }
    }

    private static bool isSame(char visit, char patternChar)
    {
        return (visit == patternChar) || (patternChar == '.');
    }

    static void Main(string[] args)
    {
        RunDotCase(); 
    }

    public static void RunTestcaseEmptyPattern()
    {
        Debug.Assert(!IsMatch("aa", "a")); 
    }

    public static void RunBasecase()
    {
        Debug.Assert(IsMatch("","a*")); 
    }

    public static void RunDotCase()
    {
        Debug.Assert(IsMatch("a",".*..a*")); 
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.