Using char[] instead of map


  • 4

    Here is my one pass char[] solution. Using char[] could be faster than map.

    public class Solution {
        public boolean canPermutePalindrome(String s) {
            int[] mem = new int[256];
            char[] cs = s.toCharArray();
            for (int i = 0; i < cs.length; i++) {
                mem[cs[i]]++;
            }
            boolean flag = true;
            for (int i = 0; i < mem.length; i++) {
                if (flag) {
                    if (mem[i]%2 != 0) {
                        flag = false;
                    }
                } else {
                    if (mem[i]%2 != 0) {
                        return false;
                    }
                }
            }
            return true;
        }
    }

  • 1

    @monkeyGoCrazy You'd better change your title from char[] to int[] because integer array is the substitute of hash map or hash set, not the char[]. Besides, another thing you speed up the algorithm is the toCharArray() which is better than charAt() method.
    The following is my one pass solution which is faster.

    public class Solution {
        public boolean canPermutePalindrome(String s) {
            int[] letters = new int[256];
            int oddCount = 0;
            for(char c: s.toCharArray()) {
                oddCount += ++letters[c] % 2 != 0 ? 1 : -1;
            }
            return oddCount <= 1;
        }
    }
    

Log in to reply
 

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