[LeetCode] 267. Palindrome Permutation II

huashiou 發布于2019-08-16 12:40 / 1082人閱讀

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]++;
            }
        }
    }
}

云服務器 GPU云服務器 Permutation palindrome LeetCode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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