Leetcode 301 - remove invalid parentheses - two linear scan, code passes Leetcode online judge

Leetcode301_removeInvalidParentheses_TwoScans.cs

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

namespace Leetcode310_removeInvalidParatheses
{
    /// <summary>
    /// Leetcode 301 - remove invalide paratheses
    /// study code: 
    /// https://discuss.leetcode.com/topic/34875/easy-short-concise-and-fast-java-dfs-3-ms-solution
    /// 
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase1();
            RunTestcase2();
            RunTestcase3();
        }

        // test case 1: "()())()" -> ["()()()", "(())()"]
        public static void RunTestcase1()
        {
            var validStrings = new List<string>();
            RemoveInvalidParatheses("()())()", validStrings, 0, 0, new char[] { '(', ')' });
        }

        // test case 2: "(a)())()" -> ["(a)()()", "(a())()"]
        public static void RunTestcase2()
        {
            var validStrings = new List<string>();
            RemoveInvalidParatheses("(a)())()", validStrings, 0, 0, new char[] { '(', ')' });
        }

        // test case 3: ")(" -> [""]
        public static void RunTestcase3()
        {
            var validStrings = new List<string>();
            RemoveInvalidParatheses(")(", validStrings, 0, 0, new char[] { '(', ')' });
        }

        public List<String> removeInvalidParentheses(String s) {
            var validStrings = new List<string>();
            RemoveInvalidParatheses(s, validStrings, 0, 0, new char[]{'(', ')'});
            return validStrings;
        }

        /// <summary>
        /// code review on August 2, 2017
        /// Function design talk:
        /// Scan the string twice, first scan is to remove the invalid ')'; 
        /// then reverse the string with removed invalid ')', in other words, scan right to left virtually, 
        /// this time is to remove invalid '('. 
        /// After removing invalid ')' and '(', reverse the search then add to validStrings list. 
        /// </summary>
        /// <param name="search"></param>
        /// <param name="validStrings"></param>
        /// <param name="start"></param>
        /// <param name="lastRemoved"></param>
        /// <param name="parenthese"></param>
        public static void RemoveInvalidParatheses(String search, List<String> validStrings, int start, int lastRemoved, char[] parenthese)
        {
            int parentheseMatch = 0;
            for (int index = start; index < search.Length; ++index)
            {
                var open  = parenthese[0];
                var close = parenthese[1]; 

                var visit = search[index];

                if (visit == open)
                {
                    parentheseMatch++;
                }

                if (visit == close)
                {
                    parentheseMatch--;
                }

                bool matching = parentheseMatch >= 0;

                if (matching)
                {
                    continue;
                }

                // Need to remove one parenthese 
                for (int position = lastRemoved; position <= index; ++position)
                {
                    if (search[position] == close && (position == lastRemoved || search[position - 1] != close))
                    {
                        var removeVisit = search.Substring(0, position) + search.Substring(position + 1);
                        RemoveInvalidParatheses(removeVisit, validStrings, index, position, parenthese);
                    }
                }

                return;
            }

            var reversedArray = search.ToCharArray();
            Array.Reverse(reversedArray); 
            var reversed = new string(reversedArray);

            // Just finished left to right, remove invalid ')'
            // need to scan from right to left
            var firstScanLeftToRight = parenthese[0] == '(';

            if (firstScanLeftToRight) 
            {
                // start to scan from right to left, to remove invalid '('
                RemoveInvalidParatheses(reversed, validStrings, 0, 0, new char[] { ')', '(' });
            }
            else 
            {
                // now both scans of from left to right and also from right to left are finished. 
                // Invalid ')' and '(' are removed. 
                // The string is the same after it is reversed twice
                validStrings.Add(reversed); 
            }
        }
    }
}