leetcode 97. Interleaving String

迷南。 2022-08-21 02:25 117阅读 0赞

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,  
Given:  
s1 = `"aabcc"`,  
s2 = `"dbbca"`,

When s3 = `"aadbbcbcac"`, return true.  
When s3 = `"aadbbbaccc"`, return false.

class Solution {
    	bool do_once(vector<pair<pair<string, string>, string>>&candi, set<pair<pair<string, string>, string>>&history)
    	{
    		vector<pair<pair<string, string>, string>>newcandi;
    		for (int i = 0; i < candi.size(); i++)
    		{
    			string s1 = candi[i].first.first;
    			string s2 = candi[i].first.second;
    			string s3 = candi[i].second;
    			for (int j = s1.length()-1; j >=0; j--)
    			{
    				if (string(s1.begin(), s1.begin() + j + 1) != string(s3.begin(), s3.begin() + j + 1))
    					continue;
    				if (j == s1.length() - 1)
    				{
    					if (s3 == s1 + s2)
    						return true;
    					continue;
    				}
    				string ss1 = string(s1.begin() + j + 1, s1.end());
    				string ss2 = s2;
    				string ss3 = string(s3.begin() + j + 1, s3.end());
    				if (history.find(pair<pair<string, string>, string>(pair<string, string>(ss1, ss2), ss3)) == history.end())
    				{
    					newcandi.push_back(pair<pair<string, string>, string>(pair<string, string>(ss1, ss2), ss3));
    					history.insert(pair<pair<string, string>, string>(pair<string, string>(ss1, ss2), ss3));
    				}
    			}
    			for (int j = s2.length()-1; j >=0; j--)
    			{
    				if (string(s2.begin(), s2.begin() + j + 1) != string(s3.begin(), s3.begin() + j + 1))
    					continue;
    				if (j == s2.length() - 1)
    				{
    					if (s3 == s2 + s1)
    						return true;
    					continue;
    				}
    				string ss2 = string(s2.begin() + j + 1, s2.end());
    				string ss1 = s1;
    				string ss3 = string(s3.begin() + j + 1, s3.end());
    				if (history.find(pair<pair<string, string>, string>(pair<string, string>(ss1, ss2), ss3)) == history.end())
    				{
    					newcandi.push_back(pair<pair<string, string>, string>(pair<string, string>(ss1, ss2), ss3));
    					history.insert(pair<pair<string, string>, string>(pair<string, string>(ss1, ss2), ss3));
    				}
    			}
    		}
    		candi = newcandi;
    		return false;
    	}
    public:
    	bool isInterleave(string s1, string s2, string s3) {
    		if (s3.length() != s1.length() + s2.length())
    			return false;
    		map<char, int>m1, m2;
    		for (int i = 0; i < s1.length(); i++)
    			m1[s1[i]]++;
    		for (int i = 0; i < s2.length(); i++)
    			m1[s2[i]]++;
    		for (int i = 0; i < s3.length(); i++)
    			m2[s3[i]]++;
    		if (m1 != m2)
    			return false;
    		if (s1.empty() && s2.empty() && s3.empty())
    			return true;
    		vector<pair<pair<string, string>, string>>candi;
    		set<pair<pair<string, string>, string>>history;
    		candi.push_back(pair<pair<string, string>, string>(pair<string, string>(s1, s2), s3));
    		bool f = false;
    		while (!f&&!candi.empty())
    		{
    			f = do_once(candi,history);
    		}
    		return f;
    	}
    };

accepted