Leetcode 10 -regular expression matching - the C# has a few bugs - the code was written on May 16, 2017, 30 minutes.

Leetcode10_May16Practice

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace StringMatchMocking
{
    class StringMatchMocking_May16Mocking
    {
        static void Main(string[] args)
        {
            bool result = isMatch("", "a*b*");
            //bool result2 = isMatch("","a*");
            Console.WriteLine(result);
        }

        static bool isMatch(string text, string pattern)
        {
            // your code goes here
            if ((text == null || text.Length == 0) &&
             (pattern == null || pattern.Length == 0))
            {
                return true;
            }

            if (text == null || text.Length == 0)
            {
                // pattern b* -> true
                // . fail  false
                // ab* fail   a*b*
                if (pattern.Length == 2 && pattern[0] != '*'
                    && pattern[1] == '*')
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }

            if (pattern == null || pattern.Length == 0)
            {
                return false;
            }

            // text is not null, pattern is not null, both not empty string 
            int left = 0;  // text 
            int right = 0; // pattern 
            int length1 = text.Length;
            int length2 = pattern.Length;
            while (left < length1 && right < length2)
            {
                var leftChar = text[left];
                var rightChar = pattern[right];

                //if(!isSpecailChar(rightChar) &&
                bool charNotEqual = leftChar != rightChar;
                bool charEqual = leftChar == rightChar;
                bool isZeroOrMore = isZeroOrMoreSequenceChar(right, pattern);

                if (!isZeroOrMore)
                {
                    if (charNotEqual) return false;
                    else
                    {
                        left++;
                        right++;
                    }
                }
                else
                {
                    // skip multiple left pointer bbbb
                    if (charEqual)
                    {
                        while (text[left] == pattern[right])
                        {
                            left++;
                        }
                    }
                    else
                    {
                        right++; // b*
                    }
                }
            }

            //edge case 
            return (left == length1 && right == length2);
        }

        private static bool isSpecialChar(char c)
        {
            return c == '.' || c == '*';
        }

        // b* pattern, b is any char, not special 
        private static bool isZeroOrMoreSequenceChar(int right, string pattern)
        {
            var current = pattern[right];
            int length = pattern.Length;

            return !isSpecialChar(current) && right < (length - 1)
            && pattern[right + 1] == '*';
        }
    }
}

// . - one char 
// * represent multiple symbol, b*, any number of b, 
// including empty string, one more b, b, bb, bbb,
// text, pattern 
// is matching or not 
// aa, pattern a 
// linear scan the string 
// linear scan 
// a - one case - not following by * 
// b* - pattern, current char = b, if it is not, does not match, return false
// continuous more b -> while loop -> continuous scan until the pattern ends
// . - text current pointer scan to next one, if there is no char, then return false
// O(n) time complexity ,  n - string, m - pattern O(n+m) -> O(math.min(n,m))
// space complexity -> two variable marks linear scan - > O(1)
// *, backward checking, *, 
// edge case: 
// 1. aa, a, -> false, second a cannot match anything, return false
// 2. aa, aa -> true
// 3. abc, a.c, -> true
// 4. abbb, ab*, bbb
// 4B. a, ab*, left text, right b*, but b* can be, matching 
// 5 acd, ab*c., -> a, c b*, keep left pointer same, pattern moves to next c c, d compare to . -> c vs b*, c !=b, => c vs c
         
         
// Text: ""      pattern :  a*b*