成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LeetCode] 267. Palindrome Permutation II

huashiou / 1104人閱讀

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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/71518.html

相關(guān)文章

  • LC 267 Palindrome Permutation II

    摘要：判斷一個能否組成一個第一次出現(xiàn)增加一，第二次出現(xiàn)減少一。出現(xiàn)偶數(shù)次的最終對被抵消。出現(xiàn)基數(shù)詞的則會讓加一。類似于，奇數(shù)個的那個單獨(dú)考慮，必須放中間。得到各個字符一半數(shù)量的長度數(shù)字的終止條件，利用的對稱性輸出結(jié)果。 Given a string s, return all the palindromic permutations (without duplicates) of it. R...

    lowett 評論0 收藏0

  • [Leetcode] Palindrome Permutation 回文變換

    摘要：最笨的方法就是用的解法，找出所有的，然后再用中判斷回文的方法來判斷結(jié)果中是否有回文。而中心對稱點(diǎn)如果是字符，該字符會是奇數(shù)次，如果在兩個字符之間，則所有字符都是出現(xiàn)偶數(shù)次。 Palindrome Permutation Given a string, determine if a permutation of the string could form a palindrome. F...

    svtter 評論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 評論0 收藏0

  • leetcode 部分解答索引（持續(xù)更新～）

    摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖恪Ｋ栽谶@里做個索引嘻嘻。 順序整理 1~50 1...

    leo108 評論0 收藏0

  • leetcode132. Palindrome Partitioning II

    摘要：題目要求現(xiàn)在有一個字符串，將分割為多個子字符串從而保證每個子字符串都是回數(shù)。我們只需要找到所有可以構(gòu)成回數(shù)的并且得出最小值即可。即將字符作為，將字符所在的下標(biāo)列表作為。再采用上面所說的方法，利用中間結(jié)果得出最小分割次數(shù)。 題目要求 Given a string s, partition s such that every substring of the partition is a ...

    jeyhan 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<