PalindromePermutation [source code]

public class PalindromePermutation {
    public boolean canPermutePalindrome(String s) {
        char[] letters = s.toCharArray();
        Set<Character> set = new HashSet<>();
        for (char c : letters) {
            if (set.contains(c)) set.remove(c);
            else set.add(c);
        }
        if (set.size() > 1) return false;
        return true;
    }

    public static void main(String[] args) {
        PalindromePermutation tester = new PalindromePermutation();
        String input1 = "abdg";
        System.out.println(tester.canPermutePalindrome(input1));
    }
}

这个是一开始用类似 SingleNumber 里面的remove duplicate的算法写的一个算法:

    public boolean canPermutePalindrome(String s) {  
        char[] letters = s.toCharArray();  
        char xor = 0;  
        for (int i = 0; i < letters.length; i++) xor ^= letters[i];  
        if (xor == 0) return true;  
        for (char c : letters)  
            if (xor == c) return true;  
        return false;  
    }

这个算法看起来很美好, linear 的时间,但是实际上是不对的, 问题就在于:

java> 'a'^'b'^'d'^'g'  
java.lang.Integer res1 = 0

其实这种 case 的存在我一开始也是知道的, 也是抱着一种碰运气的心理, 结果没想到 lc 居然真的准备了这样的 case 来防止被投机取巧;

不过能想到remove duplicate的思路来做其实就是已经找到核心问题了. 这个题目的核心思路其实还是pair remove duplicate, 只不过不能用 xor 来做了而已. 更加 general 的做法就是这里的, 用set, 其实也是很简单的.

另外回文的 legitimacy, 如果让你用一句话概括: there can be at least one char that has a odd number of occurrence.

关于保存历史信息, 不要一看到就想要用 hashmap. set 也是可以的, 事实上, 所有的都可以, 只不过hashmap 是更强力的一种而已. 这里这个用 hashmap 肯定也是可以做的, 就是麻烦一些, 因为肯定要自己判断 duplicate 了到时候. set 只是更适合这里;

速度是3ms. 最优解是0ms, 好像还是有提升空间;

Problem Description

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

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

Hide Company Tags Google Uber Bloomberg
Hide Tags Hash Table
Hide Similar Problems (M) Longest Palindromic Substring (E) Valid Anagram (M) Palindrome Permutation II (E) Longest Palindrome