[Leetcode] Palindrome Permutation 回文變換

svtter 發布于2019-08-14 12:36 / 3013人閱讀

摘要：最笨的方法就是用的解法，找出所有的，然后再用中判斷回文的方法來判斷結果中是否有回文。而中心對稱點如果是字符，該字符會是奇數次，如果在兩個字符之間，則所有字符都是出現偶數次。

Palindrome Permutation

Given a string, determine if a permutation of the string could form a palindrome.

For example, "code" -> False, "aab" -> True, "carerac" -> True.

Hint:

Consider the palindromes of odd vs even length. What difference do you notice? Count the frequency of each character. If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

哈希表法 復雜度

時間 O(N) 空間 O(N)

思路

Leetcode的提示其實已經將答案告訴我們了。最笨的方法就是用Permutations的解法，找出所有的Permutation，然后再用Palindrome中判斷回文的方法來判斷結果中是否有回文。但是我們考察一下回文的性質，回文中除了中心對稱點的字符，其他字符都會出現偶數次。而中心對稱點如果是字符，該字符會是奇數次，如果在兩個字符之間，則所有字符都是出現偶數次。所以，我們只要判斷下字符串中每個字符出現的次數，就知道該字符串的其他排列方式中是否有回文了。

注意

本題也可以用一個HashSet，第偶數個字符可以抵消Set中的字符，最后判斷Set的大小是否小于等于1就行了。

代碼

HashMap實現

public class Solution {
    public boolean canPermutePalindrome(String s) {
        Map map = new HashMap();
        // 統計每個字符的個數
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            Integer cnt = map.get(c);
            if(cnt == null){
                cnt = new Integer(0);
            }
            map.put(c, ++cnt);
        }
        // 判斷是否只有不大于一個的奇數次字符
        boolean hasOdd = false;
        for(Character c : map.keySet()){
            if(map.get(c) % 2 == 1){
                if(!hasOdd){
                    hasOdd = true;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

HashSet實現

public class Solution {
    public boolean canPermutePalindrome(String s) {
        Set set = new HashSet();
        for(int i = 0; i < s.length(); i++){
            // 出現的第偶數次，將其從Set中移出
            if(set.contains(s.charAt(i))){
                set.remove(s.charAt(i));
            } else {
            // 出現的第奇數次，將其加入Set中
                set.add(s.charAt(i));
            }
        }
        // 最多只能有一個奇數次字符
        return set.size() <= 1;
    }
}

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

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64591.html

LeetCode 精選TOP面試題【51 ~ 100】

摘要：有效三角形的個數雙指針最暴力的方法應該是三重循環枚舉三個數字。總結本題和三數之和很像，都是三個數加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復雜度為 ...

Clect 2021-11-15 11:38 評論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] 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
[Leetcode] Palindrome Number 回文數

摘要：反轉比較法復雜度時間空間思路回文數有一個特性，就是它反轉后值是一樣的。代碼逐位比較法復雜度時間空間思路反轉比較有可能會溢出，但我們遍歷每一位的時候其實并不用保存上一位的信息，只要和當前對應位相等就行了。首先，負數是否算回文。 Palindrome Number Determine whether an integer is a palindrome. Do this witho...

_Suqin 2019-08-14 12:17 評論0 收藏0
LeetCode 336. Palindrome Pairs

摘要：描述給定一組唯一的單詞，找出所有不同的索引對，使得列表中的兩個單詞，，可拼接成回文串。遍歷每一個單詞，對每一個單詞進行切片，組成和。 Description Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenatio...

TigerChain 2019-07-31 10:16 評論0 收藏0