Ugly C++ solution, but anyway it is accepted


  • 0
    J

    My solution looks ugly and lengthy. It should be optimized, but it anyway passes all the test cases. Does anyone have better solution?

    void getPalindromes(vector<string>& result, vector<char>& candidates, unordered_set<string>& hset, string s, int len) {
    	if (s.length() == len) {
    		if (hset.count(s)) return;
    		hset.insert(s);
    		result.push_back(s);
    		return;
    	}
    
    	for (int i = 0; i<candidates.size(); i++) {
    		if (candidates[i] != 0) {
    			string t = string(1, candidates[i]);
    			candidates[i] = 0;
    			getPalindromes(result, candidates, hset, t + s + t, len);
    			candidates[i] = t.front();
    		}
    	}
    }
    
    vector<string> generatePalindromes(string s) {
    	vector<string> result;
    	vector<char> candidates;
    	bool isOdd = false;
    	char oddChar;
    	int chars[256] = { 0 };
    
    	for (int i = 0; i<s.length(); i++)
    		chars[s[i]]++;
    	for (int i = 0; i<256; i++) {
    		if (chars[i] % 2 == 1) {
    			if (isOdd)
    				return result;
    			oddChar = i;
    			isOdd = true;
    		}
    
    		for (int j = 0; j<chars[i] / 2; j++)
    			candidates.push_back(i);
    	}
    
    	unordered_set<string> hset;
    	if (isOdd)
    		getPalindromes(result, candidates, hset, string(1, oddChar), s.length());
    	else
    		getPalindromes(result, candidates, hset, "", s.length());
    	return result;
    }

  • 0
    J

    I saw some smart guys using permutation to solve this problem. So, I revised my solution like below.

    void getPermutation(vector<string>& result, string s, int level) {
    	if (level == s.length()) {
    		result.push_back(s);
    		return;
    	}
    
    	for (int i = level; i<s.length(); i++) {
    		if (level < i && s[level] == s[i])
    			continue;
    
    		swap(s[level], s[i]);
    		getPermutation(result, s, level + 1);
    	}
    }
    
    vector<string> generatePalindromes(string s) {
    	vector<string> result;
    	string candidates;
    	char oddChar = 0;
    	int chars[256] = { 0 };
    
    	for (int i = 0; i<s.length(); i++)
    		chars[s[i]]++;
    	for (int i = 0; i<256; i++) {
    		if (chars[i] % 2 == 1) {
    			if (oddChar > 0) return result;
    			oddChar = i;
    		}
    
    		for (int j = 0; j<chars[i] / 2; j++)
    			candidates.push_back(i);
    	}
    
    	sort(candidates.begin(), candidates.end());
    	getPermutation(result, candidates, 0);
    
    	if (oddChar > 0) {
    		for (int i = 0; i < result.size(); i++) {
    			string t = result[i];
    			reverse(t.begin(), t.end());
    			result[i] += string(1, oddChar) + t;
    		}
    	}
    	else {
    		for (int i = 0; i < result.size(); i++) {
    			string t = result[i];
    			reverse(t.begin(), t.end());
    			result[i] += t;
    		}
    	}
    
    	return result;
    }
    

Log in to reply
 

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