5-lines simple JAVA solution with explanation


  • 21

    Explanation

    The basic idea is using HashSet to find the number of single characters, which should be at most 1.

    public boolean canPermutePalindrome(String s) {
    	Set<Character>set = new HashSet<Character>();
    	for (char c : s.toCharArray())  
    		if (set.contains(c)) set.remove(c);// If char already exists in set, then remove it from set
    		else set.add(c);// If char doesn't exists in set, then add it to set
    	return set.size() <= 1;
    }

  • 0
    D

    Isn't the time complexity O(n^2) for this method?

    Isn't it better to use hasmap and count the number of characters that have odd count a better method (O(n)) ?


  • 1

    @ChengZhang no need to use a Set. Keep counter of number of chars that have an odd count, update counter as you go, only 1 pass.

        public bool CanPermutePalindrome(string s) {
            int[] map = new int[256];
            int oddCnt = 0;
            foreach (char c in s) oddCnt += (++map[c] & 1) == 1 ? 1 : -1;
            return oddCnt <= 1;
        }
    

  • 0
    X

    @jdrogin Very nice approach! Thank you!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.