Leetcode - Permutation Palindrome ii (javascript)

 267. Palindrome Permutation II

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

Analysis:
1. start from i, first figure out if s is valid for palindrome by checking if have > 1 odd # letter. Use a map to record key-count.
2. If valid, reduce all even count/=2. If find the odd one, reduce to 0, and save odd letter.
3. DFS the left half till reach s.length/2, append to res with odd + reverse right half.

Complexity:
Time O(N!)

var s = "aasbb";
var map = {};
var res = [];
var odd = "";
if (helper(s, map)) {
    for (var key in map) {
        if (map[key] === 1) {
            odd = key;
            delete map[key];
        }
        if (map[key] % 2 === 0) {
            map[key] /= 2;
        }
    }
    dfs(map, [], res, parseInt(s.length / 2), odd);
}
console.log(res);//["absba", "basab"]

function dfs(map, path, res, len, odd) {;
    if (path.length === len) {
        res.push(path.join("") + odd + path.reverse().join(""));
        return;
    }
    for (var key in map) {
        if (map[key] === 0) {
            continue;
        }
        path.push(key);
        map[key]--;
        dfs(map, path, res, len, odd);
        path.pop();
        map[key]++;
    }
}

function helper(s, map) {
    var count = 0;
    for (var i = 0; i < s.length; i++) {
        if (map[s[i]] === undefined) {
            map[s[i]] = 0;
        }
        map[s[i]]++;
    }
    for (var key in map) {
        if (map[key] % 2 !== 0) {
            count++;
        }
        if (count > 1) {
            return false
        }
    }
    return true;
}