LC 267 Palindrome Permutation II

lowett 发布于2019-08-14 17:58 / 498人阅读

摘要：判断一个能否组成一个第一次出现增加一，第二次出现减少一。出现偶数次的最终对被抵消。出现基数词的则会让加一。类似于，奇数个的那个多带带考虑，必须放中间。得到各个字符一半数量的长度数字的终止条件，利用的对称性输出结果。

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

public class Solution {
    private List list = new ArrayList();
    
    public List generatePalindromes(String s) {
        //判断一个string能否组成panlindrome, LC 266
        int numOdds = 0;
        int[] map = new int[256];
        for(char c : s.toCharArray()){
            map[c]++;
            // 一个char第一次出现numOdds增加一，第二次出现numOdds减少一。
            // 出现偶数次的char最终对numOdds被抵消。
            // 出现基数词的char则会让numOdss加一。
            numOdds = (map[c]&1) == 1 ? numOdds+1 : numOdds - 1; 
        }
        if(numOdds > 1) return list;
        
        //类似于409 Longest Palindrome， 奇数个的那个char多带带考虑，必须放中间。
        //这里palindrome本身是对称的，所以只需要找到一半的全排列，利用对称就能得到完整的string. 
        String mid = "";
        int halfLen = 0;
        for(int i=0; i<256; i++){
            if(map[i] == 0) continue;
            // 找到那个出现奇数次的字符。
            if((map[i]&1) == 1){
                mid = "" + (char)i;
                map[i]--;
            }
            // 得到各个字符一半数量的长度
            map[i] = map[i]/2;
            halfLen += map[i];
        }
        // 数字的permutation.
        generatePalindromes("", map, halfLen, mid);
        return list;
    }
    
    public void generatePalindromes(String half, int[] map, int halfLen, String mid){
        // 终止条件，利用palindrome的对称性输出结果。
        if(half.length() == halfLen){
            StringBuilder reverse= new StringBuilder(half).reverse();
            list.add(half + mid + reverse);
            return;
        }
        
        for(int i=0; i<256; i++){
            if(map[i] > 0){
                map[i]--;
                generatePalindromes(half+(char)i, map, halfLen, mid);
                map[i]++;
            }
        }
    }
}

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

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

[LeetCode] 267. Palindrome Permutation II

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,baa...

huashiou 2019-08-16 12:40 评论0 收藏0
【LC总结】回溯 (Subsets I II/Permutation I II/Combinatio

摘要：不同数包含重复数为的时候，表示在外层的循环正在被使用，所以当前循环遇到为一定要跳过。对当前循环要添加的数组，在添加当前元素后进行递归，递归之后要将当前元素的使用标记改为，表示已经使用和递归完毕，然后再将这个元素从的末位删除。 Subsets Problem Given a set of distinct integers, nums, return all possible subse...

tuomao 2019-08-14 15:53 评论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