leetcode 301. Remove Invalid Parentheses

迈不过友情╰ 2022-08-20 02:25 13阅读 0赞

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())()"\]

")(" -> \[""\]

#include "stdafx.h"
    #include<iostream>
    #include<vector>
    #include<set>
    //#include<algorithm>
    using namespace std;
    
    
    /**
    
    "()())()" -> ["()()()", "(())()"]
    "(a)())()" -> ["(a)()()", "(a())()"]
    ")(" -> [""]
    
    */
    class Solution {
    	bool is_pure_letters(string s)
    	{
    		for (int i = 0; i < s.length(); i++)
    			if (s[i] == ')' || s[i] == '(')
    				return false;
    		return true;
    	}
    	bool trim_once(vector<pair<string,int>> &substr)
    	{
    		bool f = false;
    		set<string>container;
    		vector<pair<string, int>> newsubstr;
    		for (int i = 0; i < substr.size(); i++)
    		{
    			string tempstr = substr[i].first;
    			if (is_pure_letters(tempstr))
    			{
    				result.push_back(tempstr);
    				f = true;
    				return f;
    			}
    			/*if (substr[i].second = substr[i].first.length())
    			{
    				flag = true;
    				result.push_back(substr[i].first);
    				continue;
    			}*/
    			int count(0);
    			for (int j = substr[i].second; j < substr[i].first.length(); j++)
    			{
    				if (tempstr[j] == '(')
    					count++;
    				if (tempstr[j] == ')')
    				{
    					count--;
    					if (count < 0)
    					{
    						for (int k = j; k >= 0; k--)
    						{
    							if (tempstr[k] == ')')
    							{
    								string newstr = tempstr;
    								newstr.erase(newstr.begin()+k);
    								if (container.find(newstr) == container.end())
    								{
    									container.insert(newstr);
    									newsubstr.push_back(pair<string, int>(newstr, j));
    									
    								}
    							}
    						}
    						break;
    					}
    				}
    
    				if (j == tempstr.length() - 1)
    				{
    					if (count == 0)
    					{
    						f = true;
    						result.push_back(tempstr);
    					}
    					else if (count > 0)
    					{
    						for (int k = 0; k < tempstr.length(); k++)
    						{
    							if (tempstr[k] == '(')
    							{
    								string newstr = tempstr; 
    								newstr.erase(newstr.begin() + k);
    								if (container.find(newstr) == container.end())
    								{
    									container.insert(newstr);
    									newsubstr.push_back(pair<string, int>(newstr, 0));
    								}
    							}
    						}
    					}
    				}
    			}
    			if (substr[i].second == substr[i].first.length())
    			{
    				f = true;
    				result.push_back(substr[i].first);
    			}
    		}
    		substr = newsubstr;
    		//for (int i = 0; i < substr.size();)
    		return f;
    	}
    	int mintime;
    	vector<string>result;
    public:
    	vector<string> removeInvalidParentheses(string s) {
    		
    		int count(0),times(0);
    		mintime = s.length();
    		set<string>returnvalue;
    		vector<pair<string,int>>strs;
    		strs.push_back(pair<string,int>(s,0));
    		bool flag = trim_once(strs);
    		while (!flag)
    		{
    			flag = trim_once(strs);
    		}
    		return result;
    	}
    };
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	Solution sl;
    	vector<string>re = sl.removeInvalidParentheses(string(")()))())))"));
    	for (int i = 0; i < re.size(); i++)
    		cout << re[i].c_str() << endl;
    	system("pause");
    	return 0;
    }

acceped