Given a string, determine if a permutation of the string could form a palindrome.
For example,
Understand the problem:"code" -> False, "aab" -> True, "carerac" -> True.The problem can be easily solved by count the frequency of each character using a hash map. The only thing need to take special care is consider the length of the string to be even or odd.
-- If the length is even. Each character should appear exactly times of 2, e.g. 2, 4, 6, etc..
-- If the length is odd. One and only one character could appear odd times.
Code (Java):
public class Solution {
public boolean canPermutePalindrome(String s) {
if (s == null || s.length() <= 1) {
return true;
}
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
char letter = s.charAt(i);
if (map.containsKey(letter)) {
int count = map.get(letter) + 1;
map.put(letter, count);
} else {
map.put(letter, 1);
}
}
int tolerance = 0;
Iterator it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry pair = (Map.Entry) it.next();
if ((int) pair.getValue() % 2 != 0) {
tolerance++;
}
}
if (s.length() % 2 == 0) {
return tolerance == 0;
} else {
return tolerance == 1;
}
}
}
In this approach you are missing main palindromic check.Ex:accba
ReplyDeleteThe given string isn't palindrome but you code will return its a palindrome.
This code is correct. permutation palindrome means. some permutation of the characters will give u palindrome.
ReplyDeleteIf the length is even. Each character should appear exactly times of 2, e.g. 2, 4, 6, etc..
ReplyDelete-- If the length is odd. One and only one character could appear odd times.
In the above first statement is not correct as if length of the string is even but characters can repeat odd number of times.Example: aaab
If the length is even. Each character should appear exactly times of 2, e.g. 2, 4, 6, etc..
ReplyDelete-- If the length is odd. One and only one character could appear odd times.
In the above first statement is not correct as if length of the string is even but characters can repeat odd number of times.Example: aaab
An implementation using HashSet in C#:
ReplyDeletestatic bool HasPalindromePerm(string a_str)
{
HashSet characters = new HashSet();
foreach (char c in a_str.ToCharArray())
{
if (characters.Contains(c))
{
characters.Remove(c);
}
else
{
characters.Add(c);
}
}
if (characters.Count > 1)
{
return false;
}
return true;
}