559B. Equivalent Strings - Codeforces Solution C++ ~ CodingWithArt

➤ Problem Link : 559B. Equivalent Strings

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

map<pair<string,string>,bool > st;

bool equivalent(string s,string t)
{
	if(s==t)
		return true;
	if(s.length()%2==1)
		return false;
	if((st.find(make_pair(s,t))!=st.end() && st[make_pair(s,t)]==1) || (st.find(make_pair(t,s))!=st.end() && st[make_pair(t,s)]==1))
		return true;

	int mid=s.length()/2;
	string a1=s.substr(0,mid);
	string a2=s.substr(mid);
	string b1=t.substr(0,mid);
	string b2=t.substr(mid);

	if((equivalent(a1,b1) && equivalent(a2,b2)) || (equivalent(a1,b2) && equivalent(a2,b1)))
	{
		st[make_pair(s,t)]=1;
		return true;
	}
	return false;




}


int main()
{
	string s,t;
	cin>>s>>t;
	st.clear();
	if(equivalent(s,t))
		cout<<"YES";
	else
		cout<<"NO";

}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.