算法1

A string is a palindrome if it has exactly the same sequence of characters when read left-to-right as it has when read right-to-left. For example, the following strings are palindromes:

• "kayak",
• "codilitytilidoc",
• "neveroddoreven".

A string A is an anagram of a string B if A can be obtained from B by rearranging the characters. For example, in each of the following pairs one string is an anagram of the other:

• "mary" and "army",
• "rocketboys" and "octobersky",
• "codility" and "codility".

Write a function:

class Solution { public int isAnagramOfPalindrome(String S); }

that, given a non-empty string S consisting of N characters, returns 1 if S is an anagram of some palindrome and returns 0 otherwise.

Assume that:

• N is an integer within the range [1..100,000];
• string S consists only of lower-case letters (a−z).

For example, given S = "dooernedeevrvn", the function should return 1, because "dooernedeevrvn" is an anagram of the palindrome "neveroddoreven". Given S = "aabcba", the function should return 0.

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

 

 

解决方案：

时间复杂度和空间复杂度都能符合要求

 

public int isAnagramOfPalindrome2(String S) {
  int n = S.length();

  Vector<Character> v = new Vector<Character>(26);
  for(int i = 0; i < n; i++) {
   Character c = S.charAt(i);
   if(v.contains(c)) {//已经包含就移除，意思是出现次数为偶数的就不统计
    v.remove(c);
   } else {
    v.add(c);
   }
  }

  if(n % 2 == 0 && v.size() == 0) {//S的长度的偶数，那么各个字母的出现次数必须都是偶数
   return 1;
  } else if(n % 2 != 0 && v.size() == 1) {//S的长度是奇数，那么可以有一个字母的出现次数是奇数
   return 1;
  } else {
   return 0;
  }
 }