LeetCode -- Remove Invalid Parentheses

public class Solution {
    public IList<string> RemoveInvalidParentheses(string s) 
    {
        var ret = new List<string>();
    	var visited = new Dictionary<string, int>();
    	
    	var q = new Queue<string>();
    	q.Enqueue(s);
    	
    	var next = new Queue<string>();
    	while(q.Count > 0){
    		var str = q.Dequeue();
    		if(IsValid(str))
    		{
    			ret.Add(str);
    		}
    		else
    		{
    			for(var i = 0;i < str.Length; i++){
    				if(str[i] != ‘(‘ && str[i] != ‘)‘) continue;
    				
    				var t = str.Substring(0 , i) + str.Substring(i+1, str.Length - i - 1);
    				if(!visited.ContainsKey(t))
    				{
    					visited.Add(t , 1);
    					next.Enqueue(t);
    				}
    			}
    		}
    		
    		if(q.Count == 0){
    			if(ret.Count > 0){
    				break;
    			}
    			
    			q = new Queue<string>(next);
    			next.Clear();
    		}
    	}
    	
    	if(ret.Count == 0){
    		ret.Add("");
    	}
    	return ret;
    }


private bool IsValid(string s)
{
	
	var stack = new Stack<char>();
	for(var i = 0;i < s.Length; i++){
		if(s[i] == ‘(‘){
			stack.Push(s[i]);
		}
		else if(s[i] == ‘)‘){
			if(stack.Count == 0){
				return false;
			}
			stack.Pop();
		}
	}
	
	return stack.Count == 0;
}
}

LeetCode -- Remove Invalid Parentheses

原文：http://blog.csdn.net/lan_liang/article/details/49770495