LC: 267. Palindrome Permutation II
https://leetcode.com/problems/palindrome-permutation-ii/
267. Palindrome Permutation II
Given a string s, return all the palindromic permutations (without duplicates) of it.
You may return the answer in any order. If s has no palindromic permutation, return an empty list.
Example 1:
Input: s = "aabb"
Output: ["abba","baab"]Example 2:
Input: s = "abc"
Output: []Constraints:
1 <= s.length <= 16sconsists of only lowercase English letters.
The Essence:
Es ist hilfreich, dass man zuerst kontrolliert, ob der gegebene String zu einem Palindrom zu machen ist. Die palindromischen Strings haben ihre Zeichen in Bezug auf die Mitte gespiegelt. Man kann also zunächst ein solches Palindrom bildet, wobei man einfach die Zeichen anfänglich zufügt. Wenn man ein Zeichen auf eine Seite stellt, dann soll man das gleiche Zeichen auch auf die andere Seit stellen. Man soll also nur die Hälfte des Strings verändern, um das Palindrom zu permutieren.
Details:
Für jeden Index in dem Halbstring werden alle möglichen Zeichen versucht. Dann wird für jeden Versuch die Möglichkeiten in dem nächsten Index versucht. Die Bildung der Permutation und die implizierte Rekursion dabei entsprechen der Backtracking-Technik.
Solutions:
The further explanation of this algorithm and its code can be found here:
Default Code:
Last updated