LeetCode -- Remove Invalid Parentheses

LeetCode -- Remove Invalid Parentheses

題目描述：
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.


Note: The input string may contain letters other than the parentheses ( and ).


Examples:
()())() -> [()()(), (())()]
(a)())() -> [(a)()(), (a())()]
)( -> []




就是輸入一個字符串，其中包含了'('和')'以及字母。對這個字符串進行最小次數的刪除，假設只刪除了1次得到：str1（刪除了第i位），str2(刪除了第j位)...，strN。
將這些刪除後的字符串符合括號匹配的（就是除了字母外，'('和')'構成的是一個有效的括號字符串）加入結果集中。




思路：
1. 本題可以用DFS也可以BFS，但由於本題求的是最小次數而非第一個匹配的結果，因此BFS比較合適。
2. 如果s不符合要求，對s的第i位進行移除，i∈[0,n)，得到新字符串t1,t2,t3...判斷t[1...n]是否符合要求，如果符合要求則依次加入結果集中；否則將t[0...n)加入隊列中即可。
3. 遍歷過程中由於可能存在t已經判斷過，可使用字典來做剪枝。


實現代碼：

public class Solution {
    public IList RemoveInvalidParentheses(string s) 
    {
        var ret = new List();
    	var visited = new Dictionary();
    	
    	var q = new Queue();
    	q.Enqueue(s);
    	
    	var next = new Queue();
    	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(next);
    			next.Clear();
    		}
    	}
    	
    	if(ret.Count == 0){
    		ret.Add();
    	}
    	return ret;
    }


private bool IsValid(string s)
{
	
	var stack = new Stack();
	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;
}
}