C++ DFS solution


  • 0
    class Solution {
    private:
        int freq[256], cnt = 0;
        string midc = "";
        vector<string> ans;
        
        void gen(string& path) {
            if (path.length() == cnt) {
                ans.push_back(path + midc + string(path.rbegin(), path.rend()));
                return;
            }
            
            for (int c = 0; c < 256; c++) {
                if (freq[c]) {
                    path.push_back(c); freq[c]--;
                    gen(path);
                    path.pop_back(); freq[c]++;
                }
            }
        }
        
    public:
        vector<string> generatePalindromes(string s) {
            memset(freq, 0, sizeof(freq));
            for (char c : s) { freq[c]++; }
            
            for (int c = 0; c < 256; c++) {
                if (freq[c] & 1 == 1) {
                    if (midc.size()) {
                        return ans;     // more than one char with appeared odd number of times
                    } else {
                        midc += c;
                        freq[c]--;
                    }
                }
                freq[c] /= 2;
                cnt += freq[c];
            }
            
            string path = "";
            gen(path);
            return ans;
        }
    };
    

Log in to reply
 

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