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

1
2
3
4
5
6
7
8
Input: "code"
Output: false

Input: "aab"
Output: true

Input: "carerac"
Output: true

实际上 permutation的做法并不是必须的；只是检验能不能form a palindrome, 并没有要求返回这些palindrome，所以并没有必要记录(list, List<List<…), 如果记录很可能Memory Limit Exceeded:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean canPermutePalindrome(String s) {
        return dfs(s, "");
    }
    
    public boolean dfs(String s, String tmp) {
        if (tmp.length() == s.length() && isPalindrome(tmp)) return true;
        for (int i = 0; i < s.length(); ++i) {
            tmp += s.charAt(i);
            dfs(s, tmp);
            tmp = tmp.substring(0, tmp.length() - 1);
        }
        return false;
    }
    
    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) return false;
        }
        return true;
    }
}

实际上想想，permutation如果没有要求返回，那么任意顺序的排列，实际上就是成对出现的字母，最多有一个不成对: set记录出现的字母，有一个存入再来一个remove，看最后set的size:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean canPermutePalindrome(String s) {
        Set<Character> set = new HashSet<>();
        char[] ss = s.toCharArray();
        for (char c : ss) {
            if (!set.contains(c)) set.add(c);
            else set.remove(c);
        }
        return set.size() == 0 || set.size() == 1;
    }
}