Question

面试题 01.04. 回文排列

English Version

题目描述

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

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

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

 

示例1：

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

 

解法

方法一：哈希表

我们用哈希表 $cnt$ 存储每个字符出现的次数。若次数为奇数的字符超过 $1$ 个，则不是回文排列。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串长度。

class Solution:
  def canPermutePalindrome(self, s: str) -> bool:
    cnt = Counter(s)
    return sum(v & 1 for v in cnt.values()) < 2

class Solution {
  public boolean canPermutePalindrome(String s) {
    Map<Character, Integer> cnt = new HashMap<>();
    for (int i = 0; i < s.length(); ++i) {
      cnt.merge(s.charAt(i), 1, Integer::sum);
    }
    int sum = 0;
    for (int v : cnt.values()) {
      sum += v & 1;
    }
    return sum < 2;
  }
}

class Solution {
public:
  bool canPermutePalindrome(string s) {
    unordered_map<char, int> cnt;
    for (auto& c : s) {
      ++cnt[c];
    }
    int sum = 0;
    for (auto& [_, v] : cnt) {
      sum += v & 1;
    }
    return sum < 2;
  }
};

func canPermutePalindrome(s string) bool {
  vis := map[rune]bool{}
  cnt := 0
  for _, c := range s {
    if vis[c] {
      vis[c] = false
      cnt--
    } else {
      vis[c] = true
      cnt++
    }
  }
  return cnt < 2
}

function canPermutePalindrome(s: string): boolean {
  const set = new Set<string>();
  for (const c of s) {
    if (set.has(c)) {
      set.delete(c);
    } else {
      set.add(c);
    }
  }
  return set.size <= 1;
}

use std::collections::HashSet;

impl Solution {
  pub fn can_permute_palindrome(s: String) -> bool {
    let mut set = HashSet::new();
    for c in s.chars() {
      if set.contains(&c) {
        set.remove(&c);
      } else {
        set.insert(c);
      }
    }
    set.len() <= 1
  }
}

方法二：哈希表的另一种实现

我们用哈希表 $vis$ 存储每个字符是否出现过。若出现过，则从哈希表中删除该字符；否则，将该字符加入哈希表。

最后判断哈希表中字符的个数是否小于 $2$，若是，则是回文排列。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串长度。

class Solution:
  def canPermutePalindrome(self, s: str) -> bool:
    vis = set()
    for c in s:
      if c in vis:
        vis.remove(c)
      else:
        vis.add(c)
    return len(vis) < 2

class Solution {
  public boolean canPermutePalindrome(String s) {
    Set<Character> vis = new HashSet<>();
    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      if (!vis.add(c)) {
        vis.remove(c);
      }
    }
    return vis.size() < 2;
  }
}

class Solution {
public:
  bool canPermutePalindrome(string s) {
    unordered_set<char> vis;
    for (auto& c : s) {
      if (vis.count(c)) {
        vis.erase(c);
      } else {
        vis.insert(c);
      }
    }
    return vis.size() < 2;
  }
};