Question
Formatted question description: https://leetcode.ca/all/266.html
266 Palindrome Permutation
Given a string, determine if a permutation of the string could form a palindrome.
For example,
"code" -> False, "aab" -> True, "carerac" -> True.
Hint:
Consider the palindromes of odd vs even length. What difference do you notice?
Count the frequency of each character.
If each character occurs even number of times, then it must be a palindrome.
How about character which occurs odd number of times?
Algorithm
Use HashSet
to traverse the string
- If a letter is not in the HashSet, we add this letter,
- If the letter already exists, we delete the letter, So in the end, if there are no letters or only one letter in the HashSet, it means that it is a palindrome.
Code
Java
-
import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; public class Palindrome_Permutation { public class Solution { public boolean canPermutePalindrome(String s) { Map<Character, Integer> map = new HashMap<Character, Integer>(); for(int i = 0; i < s.length(); i++){ char c = s.charAt(i); map.put(c, 1 + map.getOrDefault(c, 0)); } int count = 0; for (int each: map.values()) { if (each % 2 == 1) { count++; } } return count < 2; } } public class Solution_set { public boolean canPermutePalindrome(String s) { Set<Character> hs = new HashSet<>(); for (char each: s.toCharArray()) { if (hs.contains(each)) { hs.remove(each); } else { hs.add(each); } } return hs.size() <= 1; } } }
-
// OJ: https://leetcode.com/problems/palindrome-permutation/ // Time: O(N) // Space: O(N) class Solution { public: bool canPermutePalindrome(string s) { int cnt[26] = {}, single = 0; for (char c : s) cnt[c - 'a']++; for (int n : cnt) { single += n % 2; if (single > 1) return false; } return true; } };
-
class Solution(object): def canPermutePalindrome(self, s): """ :type s: str :rtype: bool """ oddChars = set() for c in s: if c in oddChars: oddChars.remove(c) else: oddChars.add(c) return len(oddChars) <= 1