面试题 01.04. 回文排列
题目描述
给定一个字符串,编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。
示例1:
输入:"tactcoa" 输出:true(排列有"tacocat"、"atcocta",等等)
解法
方法一:哈希表
我们用哈希表 $cnt$ 存储每个字符出现的次数。若次数为奇数的字符超过 $1$ 个,则不是回文排列。
时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 为字符串长度。
1 2 3 4 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
方法二:哈希表的另一种实现
我们用哈希表 $vis$ 存储每个字符是否出现过。若出现过,则从哈希表中删除该字符;否则,将该字符加入哈希表。
最后判断哈希表中字符的个数是否小于 $2$,若是,则是回文排列。
时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 为字符串长度。
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|