Leetcode: Palindrome Permutation II

Palindrome Permutation II

Similar Problems:

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 [].
```

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/palindrome-permutation-ii
// Basic Ideas: permutation without duplicates
//
// Complexity: Time ? Space ?
func dfs(combination string, length int, m map[rune]int, central string, res *[]string) {
if len(combination) == length {
str := combination + central
for i:=len(combination)-1; i>=0; i-- {
str += string(combination[i])
}
*res = append(*res, str)
return
}

for i:=0; i<256; i++ {
ch := rune(i)
if m[ch] > 0 {
m[ch]--
dfs(combination+string(ch), length, m, central, res)
m[ch]++
}
}
}

func generatePalindromes(s string) []string {
m := map[rune]int{}
for _, ch := range s { m[ch]++ }
central := ""
length := 0
for key, val := range m {
if val%2 != 0 {
if central != "" {
return []string{}
}
central = string(key)
}
m[key] = val/2
length += m[key]
}
res := []string{}
dfs("", length, m, central, &res)
return res
}
```

Share It, If You Like It.