Facebook脸家 - Lexicographical path

Lexicographical path

        5
       / \
      3   2
     / \   \
    2   4   4
             \
              1

FB 面经，自底向上的 path 有【1,4,2,5】，【4,3,5】，【2,3,5】，要求按自底向上的 lexicographical order 返回排序的 path，比如在这里是 【1,4,2,5】, 【2,3,5】,【4,3,5】

Analysis: Post order, for each node keep left & right paths, merge 2 into one single path.
Complexity: O(nlgn), each node has at most lgn node in the path.

var binaryTreePaths = function(root) {
 var res = [];
 console.log(dfs(root, res));
 
 return res
};
function dfs(root, path){
    if(root === null){
 return [];
  }
  if(root.left === null && root.right === null){
      return [[root.val]];
  }
  var left = dfs(root.left, path);
  var right = dfs(root.right, path);
  var path = [];
  for(var key in left){
     left[key].push(root.val);
  }
  for(var key in right){
     right[key].push(root.val);
  }
  path = left.concat(right);
  return path;
}

Leetcode - 214. Shortest Palindrome

214. Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Analysis:
  S#S' will make a valid palindrome. Key is to use KMP algo to find existing repeating part from the half, which is S
 ex1:   aa#aa
KMP: 01012  -> so we will have s.substring(2).reverse + s = '' + 'aa' = 'aa'
ex2:   bba#abb
KMP: 0100012 -> so we will have s.substring(1).reverse +  s = 'a.reverse' + 'bba' = abba

Complexity: O(N)

var shortestPalindrome = function(s) {
    if(s.length < 1){return s;}
    var pali = s+"#"+s.split("").reverse().join("");//s#s'
   //storing next entry pos for comparision
    var kmp = getKMP(pali);
    console.log(kmp)
    var length = kmp[kmp.length-1];
    return s.substring(length).split("").reverse().join("") + s;
};

function getKMP(s){
    var j = 0;
    var table = [];
    table[0] = 0;
    for(var i = 1; i < s.length; i++){
        while(s[i] !== s[j] && j > 0){
            j = table[j-1];
        }
        if(s[i] === s[j]){
            table[i] = j+1;
            j++;
        }else{
            table[i] = 0;
        }
    }
    return table;
}

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;
}