string permutation



  • Hi,
    i want to check if one is a permutation of the other one...any comments to my approach?

    bool in_string_permutation(string &s1, string &s2) {
    	std::unordered_map<int,int> ht;
    	auto s_it = s2.begin();
    	bool check = true;
    
    	if(s1.length() != s2.length()) {
    		return false;
    	}
    
    	for_each(s1.begin(), s1.end(), [&](char &s)
    	{ 
    		// inc count
    		auto it = ht.find(s);
    		if (it != ht.end()) {
    			ht[s]++;
    		}
    		else {
    			ht.insert(std::make_pair(s, 1));
    		}
    
    		// dec count
    		auto it2 = ht.find(*s_it);
    		if (it2 != ht.end()) {
    			ht[*s_it]--;
    		}
    		else {
    			ht.insert(std::make_pair(*s_it, -1));
    		}
    
    		s_it++;
    	});
    
    	for_each(ht.begin(), ht.end(), [&](std::pair<const int, int> &p)
    	{ 
    		if(p.second != 0) {
    			check = false;
    		}
    	});
    
    	return check;
    }
    


  • bool in_string_permutation(string s1, string s2)
    {
        sort(begin(s1), end(s1);
        sort(begin(s2), end(s2);
        return s1 == s2;
    }
    


  • Looks very complicated. You should either pass const string & or string, because the function should not change the parameters passed.

    bool is_string_permutation(string s1, string s2){
        //maybe do a length check first
        sort(s1.begin(), s1.end());
        sort(s2.begin(), s2.end());
        return s1 == s2;
    }
    

    Different approach:

    bool is_string_permutation(const string s1, const string s2){
        //maybe do a length check first
        map<char, size_t> m1;
        for (const auto &c : s1)
            m1[c]++;
        map<char, size_t> m2;
        for (const auto &c : s2)
            m2[c]++;
        return m1 == m2;
    }
    

    //dammit, too late


Log in to reply