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
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.