PalindromePermutationOPT [source code]

public class PalindromePermutationOPT {
    public boolean canPermutePalindrome(String s) {
        char[] ch = s.toCharArray();
        char[] map = new char[128];
        int sum = 0;
        for (char c : ch) {
            if (map[c] == 0) {
                map[c]++;
                sum++;
            } else {
                sum--;
                map[c]--;
            }
        }
        return sum <= 1 ? true : false;
    }

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

这个是0ms 的submission最优解; 另外, 之前那个用 set 的是 discussion 的最优解;

这个算法其实是一个比较聪明的算法. 人家并不是一个简单的用 array 来实现 map (value as index, or bucket sort, counting sort, 差不多的意思) 而已这么简单的优化.

我记得前面有一个问题, 当时要求 inplace, 所以后面的最优解的做法就是用相反数的思路来完成一个occurrence counter的操作, 因为那个题目当时要判断的也是pair duplicate, 所以说是要 counter, 其实只不过是要一个 flag 一样的, 而且只要一个 flag. 一个 flag, 其实对应的就是你要有一个binary operation. 比如相反数, 就是取反一次, 和取反两次, 两个 operation, 对应的结果可以分辨就行了;

这里也是类似的, 每个 map 的entry 对应的就是用来count 每个 char 出现的次数. 不同的是 我们只有两个操作: ++和--;这样实际上每个 entry就跟上面那个例子的bit flag是一个意思 (只有0和1两个 state);

相应的, 这个算法其实是可以改成 inplace 的;

另外这里 sum 的运用也很聪明, if any ++, then sum ++, if any -- then sum --. 这样最后完成的作用就是 sum 保存的就是所有没有被抵消的occurrence的数量; 这样一个 实时 update 的 track 的使用, 也是在算法加速中很常见的, 之前好像就碰到过一次. (后面那些1ms 的算法的做法就是一个直白的全++的 counter, 然后一个一个 mod2来判断);

这个算法的设计者真的是相当的熟练;

/*
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