Work on Leetcode 301 - remove invalid parentheses - study one of the discussions.

Leetcode301_removeInvalidParentheses_practice1.cs

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

namespace Leetcode301_removeInvalidParentheses
{
    class Program
    {
        /// <summary>
        /// Leetcode 301: remove invalid parentheses
        /// Feb. 7, 2018
        /// Study Leetcode discussion:
        /// https://leetcode.com/problems/remove-invalid-parentheses/discuss/75027/Easy-Short-Concise-and-Fast-Java-DFS-3-ms-solution
        /// 
        /// Highlights of design:
        /// 1. Use recursive function
        /// 2. Find first unmatched ), and then remove all possible ) from the beginning;
        ///    make recursive call;
        /// 3. After the unmatched close brackets has been removed, and then continue to 
        ///    process unmatched open brackets. Just call the reversed array.
        /// 4. At the end of the recursive function, only when the reversed string is processed, 
        ///    add the string to the valid string list;
        /// 5. Use two pointers left and right to scan through the string, find first char in every
        ///    consecutive unmatched paretheses, add the option to remove it once.
        ///    this is a nice and smart tip to remember, code from line 75 to 83. 
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            RunTestcase(); 
        }

        static void RunTestcase()
        {
            var validStrings = removeInvalidParentheses("()())()");
            Debug.Assert(validStrings[0].CompareTo("()()()") == 0 ||
                         validStrings[0].CompareTo("(())()") == 0); 
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static List<String> removeInvalidParentheses(String s) {
            var answer = new List<String>();
            remove(s, answer, 0, 0, new char[]{'(', ')'});
            return answer;
        }

        private static void remove(String s, List<String> validStrings, int right, int left, char[] parenthese)
        {
            for (int openBracket = 0, i = right; i < s.Length; ++i)
            {
                var current = s[i];
                if (current == parenthese[0])
                {
                    openBracket++;
                }

                if (current == parenthese[1])
                {
                    openBracket--;
                }

                if (openBracket >= 0)
                {
                    continue;
                }

                // find first unmatched parenthese, and then go over all the options to remove it.
                for (int j = left; j <= i; ++j)
                {
                    if (s[j] == parenthese[1] && (j == left || s[j - 1] != parenthese[1]))
                    {
                        // remove s[j]
                        var stringAfterRemove = s.Substring(0, j) + s.Substring(j + 1);
                        remove(stringAfterRemove, validStrings, i, j, parenthese);
                    }
                }

                return;
            }

            var reversed = new String(s.ToCharArray().Reverse().ToArray());

            if (parenthese[0] == '(') // finished left to right
            {
                remove(reversed, validStrings, 0, 0, new char[] { ')', '(' });
            }
            else // finished right to left
            {
                validStrings.Add(reversed);
            }
        }
    }
}