01.04.回文排列

面试题 01.04. 回文排列

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。

回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。

回文串不一定是字典当中的单词。

示例1：

输入：“tactcoa” 输出：true（排列有"tacocat”、“atcocta”，等等）

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/palindrome-permutation-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

能排列成回文排列的，有两种情况

每个字符都是 2 个
除中间字符外，其余字符都是 2 个
用 HashSet 保存遍历过的字符串
遍历时，如果set中包含，则把set中包含的删除
如果不包含，则加入set
最终set中有0个或者 1个元素，则为回文排列

代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


    // 能排列成回文排列的, 有两种情况
    // 1， 每个字符都是两个
    // 2， 中间字符1个，其余字符都是两个
    // 所以 遍历字符串，Set中不包含元素时，添加。
    // Set中包含元素时，把包含的元素删除(抵消)
    // 最终Set中有 0个 或者 1个元素。则为回文排列
    public boolean canPermutePalindrome(String s) {

        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (set.contains(c)){
                set.remove(c);
            }else {
                set.add(c);
            }
        }

        return set.size() <= 1;
    }

时间复杂度 : O(N) 遍历一遍字串

空间复杂度 : O(N) 额外的set存储空间

Contents

面试题 01.04. 回文排列

题解：