leetcode - Remove Invalid Parentheses

2014 단어 leetcode
제목:
https://leetcode.com/problems/remove-invalid-parentheses/
생각:
넓이를 우선적으로 훑어보다.최종 결과res로 돌아가기 전에 주의하세요!
class Solution
{
public:
	// kuohao cur , kuohao 
	void removeInvalidParentheses_core(string &s,int begin,int kuohao,string &cur,vector &res)
	{
		//s[begin] '(' ')'
		if(begin==s.size())// 
		{
			if(kuohao!=0)
				return;
			if(res.empty() || res[0].size()==cur.size())
				res.push_back(cur);
			if(!res.empty() && res[0].size()s.size())
			return;
		if(s[begin]=='(' && (s.size()-begin-1>=1+kuohao))
		{
			int yaru=1,tmp_kuohao=kuohao;
			cur.push_back(s[begin]);
			int i=begin+1;
			++tmp_kuohao;

			while(i0)
			{
				cur.pop_back();
				--yaru;
			}

		}
		else if(s[begin]==')' && kuohao>0)
		{
			int yaru=1,tmp_kuohao=kuohao;
			cur.push_back(s[begin]);
			int i=begin+1;
			--tmp_kuohao;

			while(i0)
			{
				cur.pop_back();
				--yaru;
			}
		}
		// s[begin]
		int i=begin;
		i++;
		int yaru=0;
		while(i0)
		{
			cur.pop_back();
			--yaru;
		}
	}

	vector removeInvalidParentheses(string s)
	{
		if(s.empty())
		{
			return vector(1,"");
		}
		if(s.size()==1)
		{
			if(s[0]=='('||s[0]==')')
				s.pop_back();
			return vector(1,s);
		}

		int i=0;//s[i] '('
		while(i(1,cur);
		}
		vector res;
		removeInvalidParentheses_core(s,i,0,cur,res);
		sort(res.begin(),res.end());
		res.erase(unique(res.begin(),res.end()),res.end());
		return res;
	}
};

좋은 웹페이지 즐겨찾기