题目描述：
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; } }
?
|