LC: Palindrome Permutation II - spiralgo/algorithms GitHub Wiki

Palindrome Permutation II

The Essence:

• Sanity checks before running an algorithm is essential in many programs. Hence, to check if the string can be permuted into a palindrome is helpful. No palindrome contains more than a single character that occurs odd number of times.

• Strings that are palindromes have their chars mirrored from the middle. So, an initial palindrome with all the characters of the string laid out can be used.

• Putting a character on one side means changing the other side too. With this, the initialization as well as the permutation of the string only depends on changing half of the string.

Details:

For each index in the half-string, all possible choices will be tested, then the procedure will move on to the next index. This continues until the half-string is completed. The creation of permutations and combinations of a list usually involve backtracking.

The further explanation of this algorithm and its code can be found here: https://github.com/spiralgo/algorithms/pull/310