Daily Archives: January 20, 2016

Palindrome Permutation II

This one is from leetcode. 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 [].

Solution. We should get string where each unique char is only half number of original string. We permutate it. Then we add the result with the reverse part. For example, for “aabb”, we should get all permutation of “ab”, which are “ab” and “ba”. Then we add the reverse part, and we have “abba”, “baab”.

Besides, another case is when there is an odd char. We should put it in the middle position.

Check my code on github: link

Permutation II

https://leetcode.com/problems/permutations-ii/

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

Solution. Solution is inspired from here. This is a very good one. First we sort the array. We should set a a used[] array. When we use num[i], if num[i] == num[i – 1], we should check if we move on. If num[i] == num[i – 1], and num[i – 1] is not used, then we shouldn’t move on.

This is a very good case for permutation. I have other permutation case from here.

check my code on github: link