[LeetCode] 267. Palindrome Permutation II

huashiou 发布于2019-08-16 12:40 / 996人阅读

Problem

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

Example

Given s = "aabb", return ["abba","baab"].
Given s = "abc", return [].

Solution

class Solution {
    public List generatePalindromes(String s) {
        List res = new ArrayList<>();
        if (s == null || s.length() == 0) return res;
        
        //create a map to record counts of chars: int[256]
        //count the chars that have odd number of count: <= 1 means valid palindrome
        int[] map = new int[256];
        int odd = 0;
        for (char ch: s.toCharArray()) {
            map[ch]++;
            if ((map[ch]&1) == 1) odd++;
            else odd--;
        }
        if (odd > 1) return res;
        
        //get mid string: should have length of 1 or 0
        String mid = "";
        int halfLen = 0;
        for (int i = 0; i < 256; i++) {
            if (map[i] > 0) {
                //find the odd counted char, add to mid
                if ((map[i]&1) == 1) {
                    mid += (char)i;
                    map[i]--;
                }
                //reduce count to half for each char
                map[i] /= 2;
                //update half palindrome length
                halfLen += map[i];
            }
        }
        
        dfs(map, "", mid, halfLen, res);
        return res;
    }
    
    private void dfs(int[] map, String temp, String mid, int len, List res) {
        if (temp.length() == len) {
            StringBuilder sb = new StringBuilder(temp).reverse();
            res.add(temp+mid+sb.toString());
            return;
        }
        for (int i = 0; i < 256; i++) {
            if (map[i] > 0) {
                map[i]--;
                dfs(map, temp+(char)i, mid, len, res);
                map[i]++;
            }
        }
    }
}

专线服务云服务器 Permutation palindrome LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71518.html

LC 267 Palindrome Permutation II

摘要：判断一个能否组成一个第一次出现增加一，第二次出现减少一。出现偶数次的最终对被抵消。出现基数词的则会让加一。类似于，奇数个的那个单独考虑，必须放中间。得到各个字符一半数量的长度数字的终止条件，利用的对称性输出结果。 Given a string s, return all the palindromic permutations (without duplicates) of it. R...

lowett 2019-08-14 17:58 评论0 收藏0
[Leetcode] Palindrome Permutation 回文变换

摘要：最笨的方法就是用的解法，找出所有的，然后再用中判断回文的方法来判断结果中是否有回文。而中心对称点如果是字符，该字符会是奇数次，如果在两个字符之间，则所有字符都是出现偶数次。 Palindrome Permutation Given a string, determine if a permutation of the string could form a palindrome. F...

svtter 2019-08-14 12:36 评论0 收藏0
[LeetCode] 266. Palindrome Permutation

Problem Given a string, determine if a permutation of the string could form a palindrome. Example 1: Input: codeOutput: falseExample 2: Input: aabOutput: trueExample 3: Input: careracOutput: true Solu...

jlanglang 2019-08-16 13:38 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
leetcode132. Palindrome Partitioning II

摘要：题目要求现在有一个字符串，将分割为多个子字符串从而保证每个子字符串都是回数。我们只需要找到所有可以构成回数的并且得出最小值即可。即将字符作为，将字符所在的下标列表作为。再采用上面所说的方法，利用中间结果得出最小分割次数。题目要求 Given a string s, partition s such that every substring of the partition is a ...

jeyhan 2019-08-15 14:27 评论0 收藏0