Leetcode 301 - remove invalid parentheses - using breadth first search

Leetcode301-removeInvalidParentheses_BFS.cs

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

namespace Leetcode301_removeInvalidParentheses_BFS
{
    /// <summary>
    /// study BFS 
    /// discussion link is https://discuss.leetcode.com/topic/28855/java-bfs-solution-16ms-avoid-generating-duplicate-strings/2
    /// 
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
            //RunTestcase1();
            RunTestcase2();
            //RunTestcase3();
        }

        // test case 1: "()())()" -> ["()()()", "(())()"]
        public static void RunTestcase1()
        {            
            var validStrings = removeInvalidParentheses("()())()");
        }

        // test case 2: "(a)())()" -> ["(a)()()", "(a())()"]
        public static void RunTestcase2()
        {
            var validStrings = removeInvalidParentheses("(a)())()");
        }

        // test case 3: ")(" -> [""]
        public static void RunTestcase3()
        {
            var validStrings = removeInvalidParentheses(")(");
        }

        public static List<String> removeInvalidParentheses(String s) {
            if (isValid(s))
            {               
                var list = new List<String>(); 
                list.Add(s); 
                return list;
            }

            var matchingOnes = new List<String>();

            //The queue only contains invalid middle steps
            var queue = new Queue<Tuple>();

            //The 3-Tuple is (string, startIndex, lastRemovedChar)
            queue.Enqueue(new Tuple(s, 0, ')'));

            while (queue.Count > 0) {
                Tuple current = queue.Dequeue();
                var search  = current.Search;
                var start   = current.Start;
                var removed = current.Removed; 

                //Observation 2, start from last removal position
                for (int index = start; index < search.Length; ++index)
                {
                    var visit = search[index];

                    //Not parentheses
                    bool isParenthese = visit == '(' || visit == ')';
                    if (!isParenthese)
                    {
                        continue;
                    }

                    //Observation 1, do not repeatedly remove from consecutive ones
                    if (index != start && search[index - 1] == visit)
                    {
                        continue;
                    }

                    //Observation 3, do not remove a pair of valid parentheses
                    if (removed == '(' && visit == ')')
                    {
                        continue;
                    }

                    // remove visit char from the string
                    var candidate = search.Substring(0, index) + search.Substring(index + 1);

                    //Check isValid before add
                    if (isValid(candidate))
                    {
                        matchingOnes.Add(candidate);
                    }
                    //Avoid adding leaf level strings
                    else if (matchingOnes.Count == 0)
                    {
                        queue.Enqueue(new Tuple(candidate, index, visit));
                    }
                }
            }

            return matchingOnes;
        }
                
        /// <summary>
        /// test case: 
        /// "()","(())", "()()"  true
        /// ")(","())"  false, 
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static bool isValid(String s) {
            int count = 0;
            for (int i = 0; i < s.Length; ++i) {
                var visit = s[i];
                bool isOpen  = visit == '(';
                bool isClose = visit == ')';
                if (isOpen)
                {
                    ++count;
                }

                if (isClose)
                {
                    bool noOpenToMatch = count <= 0;

                    if (noOpenToMatch)
                    {
                        return false;                     
                    }
                    
                    count--;                                       
                }
            }

            return count == 0;
        }

        private class Tuple {
            public  String Search;
            public  int    Start;
            public  char   Removed;

            public Tuple(String string1, int start, char removed) {
                this.Search  = string1;
                this.Start   = start;
                this.Removed = removed;
            }
        }
    }
}