C++ AC code using recursion and hash-map


  • 0
    C

    Idea:

    (str1,str2) is a scramble pair when :

    1. there exist an i, such that both (str1[0:i],str2[0:i]) and (str[i:end],str[i:end]) are scramble pairs;
      or
    2. there exist an i, such that both (str1[0:i],str2[i:end]) and (str[i:end],str[0:i]) are scramble pairs;

    once str1 and str2 are determined, hash_map[str1+str2] can be set to the flag, as well as hash_map[str2+str1]

    some acceleration can be added before recurse such as check whether s1==s2 and hist[s1]==hist[s2];

    class Solution {
    public:
    	unordered_map <string,bool> map;
        bool isScramble(string s1, string s2) {
            int n = s1.length();
            if(n!=s2.length()) return false;
            if(n==1) return s1[0]==s2[0];
            if(s1==s2) return true;
            bool comp = false;
            if(map.count(s1+s2)>0)
            {
            	comp = map[s1+s2];
            }
            else
            {
            	int hist1[128]={0};
            	int hist2[128]={0};
            	for(int i = 0; i<n; i++)
            	{
            		hist1[s1[i]]++;
            		hist2[s2[i]]++;
            	}
            	comp = true;
            	for(int i = 0; i<128; i++)
            	{
            		if(hist1[i]!=hist2[i])
            		{
            			comp = false;
            			break;
            		}
            	}
            	if(comp)
            	for(int i = 1; i<n; i++)
            	{ 	
                	comp = isScramble(s1.substr(0,i),s2.substr(n-i,i));
                	comp = comp && isScramble(s1.substr(i),s2.substr(0,n-i));
                	bool comp1 = isScramble(s1.substr(0,i),s2.substr(0,i));
                	comp1 = comp1 && isScramble(s1.substr(i),s2.substr(i));
                	comp = comp || comp1;
                	if(comp) break;
                }
                map[s1+s2]=comp;
                map[s2+s1]=comp;
            }
            //cout<<s1<<"|"<<s2<<"|"<<comp<<endl;
            return comp;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.