266.Palindrome-Permutation

266. Palindrome Permutation

题目地址

https://leetcode.com/problems/palindrome-permutation/

题目描述

Given a string, determine if a permutation of the string could form a palindrome.

Example 1:
Input: "code"
Output: false

Example 2:
Input: "aab"
Output: true

Example 3:
Input: "carerac"
Output: true

代码

Approach #1 Brute Force

If a string with an even length is a palindrome, every character in the string must always occur an even number of times. If the string with an odd length is a palindrome, every character except one of the characters must always occur an even number of times. Thus, in case of a palindrome, the number of characters with odd number of occurences can't exceed 1(1 in case of odd length and 0 in case of even length).

class Solution {
  public boolean canPermutePalindrome(String s) {
        int count = 0;
    for (char i = 0; i < 128 && count <= 1; i++) {
      int ct = 0;
      for (int j = 0; j < s.length(); j++) {
        if (s.charAt(j) == i) {
          ct++;
        }
      }
           count += ct % 2;
    }

    return count <= 1;
  }
}

Approach #2 Using HashMap

class Solution {
  public boolean canPermutePalindrome(String s) {
    HashMap<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
      map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
    }
    int count = 0;
    for (char key: map.keySet()) {
      count += map.get(key) % 2;
    }
    return count <= 1;
  }
}

Approach #3 Using Array

class Solution {
  public boolean canPermutePalindrome(String s) {
    int[] map = new int[128];
    for (int i = 0; i < s.length(); i++) {
      map[s.charAt(i)]++;
    }
    int count = 0;
    for (int key = 0; key < map.length && count <= 1; k++) {
      cont += map[key] % 2;
    }

    return count <= 1;
  }
}

Approach #4 Single Pass

class Solution {
  public boolean canPermutePalindrome(String s) {
    int[] map = new int[128];
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
      map[s.charAt(i)]++;
      if (map[s.charAt(i)] % 2 == 0) {
        count--;
      } else {
        count++;
      }
    }
    return count <= 1;
  }
}

Approach #5 Using Set

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

    return set.size() <= 1;
  }
}