C++ AC solution time complex O(n/2 !) and O(n) space


  • 0
    T

    class Solution {
    public:
    string midStr;
    vector<string> ret;
    void bt(unordered_map<char, int>& res, int target, string cur) {
    if (cur.size() == target) {
    string rev = cur;
    reverse(rev.begin(), rev.end());
    ret.push_back(cur + midStr + rev);
    return;
    }
    for (auto i = res.begin(); i != res.end(); i++) {
    char c = i->first;
    if (res[c]) {
    res[c] -= 2;
    bt(res, target, cur + string(1, c));
    res[c] += 2;
    }
    }
    }
    vector<string> generatePalindromes(string s) {
    midStr = "";
    unordered_map<char, int> res;
    int num = s.size();
    if (num <= 1) return {s};
    for (int i = 0; i < num; i++) res[s[i]]++;
    int count = 0;
    char oddIdx;
    for (auto i = res.begin(); i != res.end(); i++) {
    if (res[i->first] % 2) {
    count++;
    oddIdx = i->first;
    }
    }
    if (count > 1) return {};
    midStr = count == 1 ? string(1, oddIdx) : "";
    if (count == 1) res[oddIdx]--;
    string cur = "";
    bt(res, num / 2, cur);
    return ret;
    }
    };


Log in to reply
 

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