[Leetcode] Palindrome Permutation 回文变换

svtter 发布于2019-08-14 12:36 / 2923人阅读

摘要：最笨的方法就是用的解法，找出所有的，然后再用中判断回文的方法来判断结果中是否有回文。而中心对称点如果是字符，该字符会是奇数次，如果在两个字符之间，则所有字符都是出现偶数次。

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

云服务器混合云 Permutation palindrome LeetCode LeetCode_String

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

转载请注明本文地址：https://www.ucloud.cn/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