算法一

算法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;
  ??}
  ?}