leetcode 10. Regular Expression Matching

桃扇骨 2022-07-28 11:58 128阅读 0赞

Implement regular expression matching with support for `'.'` and `'*'`.

'.' Matches any single character.
    '*' Matches zero or more of the preceding element.
    
    The matching should cover the entire input string (not partial).
    
    The function prototype should be:
    bool isMatch(const char *s, const char *p)
    
    Some examples:
    isMatch("aa","a") → false
    isMatch("aa","aa") → true
    isMatch("aaa","aa") → false
    isMatch("aa", "a*") → true
    isMatch("aa", ".*") → true
    isMatch("ab", ".*") → true
    isMatch("aab", "c*a*b") → true

这题挺难的，虽然我写的迭代算法效率还算高，但他妈的又臭又长，实在懒得看第二遍,就让它过了吧。

445 / 445 test cases passed.  
Status: Accepted  
Runtime: 28 ms

class Solution {
    	bool do_once(vector<pair<string, string>>&candi, set<pair<string, string>>&hist)
    	{
    		vector<pair<string, string>>newcandi;
    		for (int i = candi.size()-1; i >=0; i--)
    		{
    			string ss = candi[i].first;
    			string pp = candi[i].second;
    			if (ss == pp)
    				return true;
    			if (pp.find('.') == string::npos&&pp.find('*') == string::npos)
    				continue;
    			int hh = 0;
    			int cc1 = 0;
    			while (hh < pp.length() && pp[hh] == '.' || pp[hh] == '*')
    			{
    				cc1 += pp[hh] == '*' ? 1 : 0;
    				hh++;
    			}
    			if (hh == pp.length())
    			{
    				if (cc1>0&&ss.length() >= pp.length() - 2 * cc1)
    					return true;
    				if (cc1 == 0 && ss.length() == pp.length())
    					return true;
    				continue;
    			}
    			int hr = hh;
    			while (hr < pp.length() && pp[hr] != '.'&&pp[hr] != '*')
    				hr++;
    			if (hr < pp.length() && pp[hr] == '*')
    			{
    				string str = string(pp.begin() + hh, pp.begin() + hr - 1);
    				string ggg = string(pp.begin() + hr + 1, pp.end());
    				int bbb = 0;
    				if (hh == 0)
    				{
    					while (ss.length() >= str.length()+bbb)
    					{
    						string str1 = str + string(bbb, pp[hr - 1]);
    						if (string(ss.begin(), ss.begin() + str1.length()) == str1)
    						{
    							string gg = string(ss.begin() + str1.length(), ss.end());
    							if (hist.find(pair<string, string>(gg, ggg)) == hist.end())
    							{
    								hist.insert(pair<string, string>(gg, ggg));
    								newcandi.push_back(pair<string, string>(gg, ggg));
    							}
    						}
    						else
    							break;
    						bbb++;
    					}
    				}
    				else
    				{
    					if (cc1 > 0)
    						while (true)
    						{
    							string str1 = str + string(bbb, pp[hr - 1]);
    							int pos = ss.find(str1);
    							if (pos != string::npos)
    							{
    								while (pos != string::npos)
    								{
    									if (pos >= hh - 2 * cc1)
    									{
    										string gg = string(ss.begin() + pos+str1.length(), ss.end());
    										if (hist.find(pair<string, string>(gg, ggg)) == hist.end())
    										{
    											hist.insert(pair<string, string>(gg, ggg));
    											newcandi.push_back(pair<string, string>(gg, ggg));
    										}
    									}
    									pos = ss.find(str1, pos + 1);
    								}
    							}
    							else
    								break;
    							bbb++;
    						}
    					else
    					{
    						while (hh + str.length() + bbb <= ss.length())
    						{
    							string str1 = str + string(bbb, pp[hr - 1]);
    							if (string(ss.begin() + hh, ss.begin() +hh+ str1.length()) == str1)
    							{
    								string gg = string(ss.begin() + hh + str1.length(), ss.end());
    								if (hist.find(pair<string, string>(gg, ggg)) == hist.end())
    								{
    									hist.insert(pair<string, string>(gg, ggg));
    									newcandi.push_back(pair<string, string>(gg, ggg));
    								}
    							}
    							else
    								break;
    							bbb++;
    						}
    					}
    				}
    			}
    			else
    			{
    				string str = string(pp.begin() + hh, pp.begin() + hr);
    				string ggg = string(pp.begin() + hr, pp.end());
    				if (hh == 0)
    				{
    					if (string(ss.begin(), ss.begin() + str.length()) == str)
    					{
    						string gg = string(ss.begin() + str.length(), ss.end());
    						if (hist.find(pair<string, string>(gg, ggg)) == hist.end())
    						{
    							hist.insert(pair<string, string>(gg, ggg));
    							newcandi.push_back(pair<string, string>(gg, ggg));
    						}
    					}
    				}
    				else
    				{
    					if (cc1 > 0)
    					{
    						int pos = ss.find(str);
    						if (pos != string::npos)
    						{
    							while (pos != string::npos)
    							{
    								if (pos >= hh - 2 * cc1)
    								{
    									string gg = string(ss.begin() + pos + str.length(), ss.end());
    									if (hist.find(pair<string, string>(gg, ggg)) == hist.end())
    									{
    										hist.insert(pair<string, string>(gg, ggg));
    										newcandi.push_back(pair<string, string>(gg, ggg));
    									}
    								}
    								pos = ss.find(str, pos + 1);
    							}
    						}
    					}
    					else
    					{
    						if (string(ss.begin() + hh, ss.begin() + hh + str.length()) == str)
    						{
    							string gg = string(ss.begin() + hh + str.length(), ss.end());
    							if (hist.find(pair<string, string>(gg, ggg)) == hist.end())
    							{
    								hist.insert(pair<string, string>(gg, ggg));
    								newcandi.push_back(pair<string, string>(gg, ggg));
    							}
    						}
    					}
    				}
    			}
    		}
    		candi = newcandi;
    		return false;
    	}
    public:
    	bool isMatch(string s, string p) {
    		if (s == p)
    			return true;
    		int pos = p.find('*');
    		while (pos != string::npos)
    		{
    			if (pos + 2 < p.length() && p[pos - 1] == p[pos + 1] && p[pos] == p[pos + 2])
    				p.erase(pos + 1, 2);
    			else
    				pos = p.find('*', pos + 1);
    		}
    		vector<pair<string, string>>candi;
    		candi.push_back(pair<string, string>(s, p));
    		bool f = false;
    		set<pair<string, string>>hist;
    		while (!candi.empty()&&!f)
    		{
    			f = do_once(candi,hist);
    		}
    		return f;
    	}
    };