面试题 01.04 回文排列

Posted on | In
Words count in article: 500 | Reading time ≈ 2

题目

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

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

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

示例1:

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

解法

解法一：

计数字符法。

统计所有的字符出现的次数，如果每个字符出现的次数都是偶数，或者出现奇数个数的字符只有一个，那么就是一个回文字符串。

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean canPermutePalindrome(String s) {
		Map<Character, Integer> map = new HashMap<>();
		
		for (char c : s.toCharArray()) {
			if (map.containsKey(c)) {
				map.replace(c, map.get(c) + 1);
			} else {
				map.put(c, 1);
			}
		}
		
		boolean allEven = true;
		int countOdd = 0;
		for (int value : map.values()) {
			if (value % 2 == 1) {
				allEven = false;
				countOdd++;
			}
		}
		
		return (1 == countOdd || allEven);
    }

解法二：

使用位运算。参考https://leetcode-cn.com/problems/palindrome-permutation-lcci/solution/shuang-bai-wei-tu-fang-fa-by-1ujin/

判断出现奇数次的字符最多只有一个（该字符将会出现在中点位置）。全体字符有128个，可以用高低两个 long 类型的位图表示128位。通过将 1L 左移，例如 ‘A’ 的 ASCII 值为65，就向左移动65位，所以位图的从第0位向左数第65位表示 ‘A’，以此类推。0 ~ 63 放在低位，64 ~ 127 放在高位。如果是0与1异或是1：0 ^ 1 = 1，1再与1异或又变回0：1 ^ 1 = 0，所以0代表该位上得字符出现偶数次。最后利用Long.bitCount()统计一下1的数量，是否小于等于1，即是否最多只有1个字符出现奇数次。

JAVA

1
2
3
4
5
6
7
8
9
10
11
public boolean canPermutePalindrome(String s) {
        long highBmp = 0, lowBmp = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= 64) {
                highBmp ^= 1L << s.charAt(i) - 64;
            } else {
                lowBmp ^= 1L << s.charAt(i);
            }
        }
        return Long.bitCount(highBmp) + Long.bitCount(lowBmp) <= 1;
    }
0%