Leetcode 301 - BFS pruning idea

Leetcode301_BFSPruning.cs

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

namespace Leetcode301_removeInvalidParentheses_UsingQueue
{
    class Program
    {
        /// <summary>
        /// code study:
        /// https://leetcode.com/problems/remove-invalid-parentheses/discuss/75032/Share-my-Java-BFS-solution
        /// Feb. 7, 2018
        /// Highlights of the design:
        /// 1. generate all possible substrings
        /// 2. check one by one on those substring and see if it is valid or not. 
        /// </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);
        }

        public static List<String> removeInvalidParentheses(String s) {
          var res = new List<string>();      
          
          if (s == null)
          {
              return res;
          }
      
          var visited = new HashSet<string>();
          var queue   = new Queue<string>();
      
          // initialize
          queue.Enqueue(s);
          visited.Add(s);
      
          var found = false;
      
          while (queue.Count > 0) {
            s = queue.Dequeue();
        
            if (isValid(s)) {              
              res.Add(s);
              found = true;
            }

            if (found)
            {
                continue;
            }
      
            // generate all possible states
            for (int i = 0; i < s.Length; i++) 
            {
                // we only try to remove left or right parenthese
                var current = s[i];
                if (current != '(' && current != ')')
                {
                    continue;
                }
        
                // remove current char s[i] 
                var substring = s.Substring(0, i) + s.Substring(i + 1);
        
                if (!visited.Contains(substring)) {
                    // for each state, if it's not visited, add it to the queue
                    queue.Enqueue(substring);
                    visited.Add(substring);
                }
            }
          }
      
          return res;
        }

        // helper function checks if string s contains valid parantheses
        private static bool isValid(String s)
        {
            int count = 0;

            for (int i = 0; i < s.Length; i++)
            {
                var c = s[i];

                if (c == '(')
                {
                    count++;
                }

                if (c == ')' && count-- == 0)
                {
                    return false;
                }
            }

            return count == 0;
        }
    }
}