3ms Java LinkedHashMap and use array to do permutation


  • 0
    Q

    Count characters with linkedhashmap, do permutation using arrays

    public class Solution {
        public List<String> generatePalindromes(String s) {
            List<String> result = new ArrayList<String>();
            if(s.length() < 2){
                result.add(s);
                return result;
            }
            char[] ca = s.toCharArray();
            if(!canPermutePalindrome(ca)){
                return result;
            }
            LinkedHashMap<Character, Integer> map = new LinkedHashMap<Character, Integer>();
            for(int i = 0; i < ca.length; ++i){
                int count = map.containsKey(ca[i]) ? map.get(ca[i]) : 0;
                map.put(ca[i], count + 1);
            }
            Character[] cArray = map.keySet().toArray(new Character[map.keySet().size()]);
            Integer[] iArray = map.values().toArray(new Integer[map.values().size()]);
            char[] rArray = new char[ca.length];
            int head = (rArray.length-1)/2, tail = head + 1;
            for(int i =0; i < iArray.length; ++i){
                if(iArray[i] % 2 == 1){
                    rArray[head--] = cArray[i];
                    iArray[i]--;
                    break;
                }
            }
            generatePalindrom(cArray, iArray, rArray,head,tail, result);
            return result;
        }
        public void generatePalindrom(Character[] cArray, Integer[] iArray, char[] rArray, int head, int tail, 
                    List<String> result){
            if(head < 0){
                result.add(new String(rArray));
                return;
            }
            for(int i = 0; i < cArray.length; ++i){
                if(iArray[i] > 0){
                    rArray[head] = cArray[i];
                    rArray[tail] = cArray[i];
                    iArray[i] -= 2;
                    generatePalindrom(cArray, iArray, rArray,head-1,tail+1, result);
                    iArray[i] += 2;
                }
            }
        }
        public boolean canPermutePalindrome(char[] ca) {
            int[] map = new int[256];
            int sigCnt = 0;
            for(int i = 0; i < ca.length; ++i){
                map[ca[i]]++;
                if(map[ca[i]] % 2 == 1){
                    sigCnt++;
                }
                else{
                    sigCnt--;
                }
            }
            return sigCnt < 2;
        }
    }

Log in to reply
 

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