Backtrack java solution, look for improvement


  • 0
    L
    public List<String> generatePalindromes(String s) {
        Map<Character,Integer> map = new HashMap<Character,Integer>();
    
        char[] str = s.toCharArray();
        for(char c: str){
            if(!map.containsKey(c)){
                map.put(c,1);
            }else{
                map.put(c,map.get(c)+1);
            }
        }
    
        List<String> result = new ArrayList<String>();
        // 只允许最多一个奇数个
        int oddCnt = 0;
        char oddChar = '0';
        int oddNum = 0;
        for(Map.Entry<Character,Integer> entry:map.entrySet()){
            if(entry.getValue()%2==1){
                ++oddCnt;
                if(oddCnt > 1){
                    return result;
                }else{
                    oddChar = entry.getKey();
                    oddNum = entry.getValue();
                }
            }
        }
    
        StringBuilder sb = new StringBuilder();
        // construct the half array
        for(Map.Entry<Character,Integer> entry:map.entrySet()){
            int cnt = entry.getValue();
            char c = entry.getKey();
            if(cnt%2 == 0){
                for (int i = 0; i < cnt/2; i++) {
                    sb.append(c);
                }
            }
        }
    
        if(oddCnt > 0){
            for (int i = 0; i < oddNum/2; i++) {
                sb.append(oddChar);
            }
        }
    
    
        //套用palindrome II
        backtrack(result,"",sb.toString().toCharArray(),0,oddCnt,oddChar);
        return result;
    }
    
    
    private void backtrack(List<String> result,String cur,char[] s,int start,int oddCnt,char oddChar){
        if(start == s.length){
            result.add(halfToFull(cur,oddCnt,oddChar));
            return;
        }
    
        // 不用nums[i-1]==nums[i]规避重复而用map类似visited,因为过程中swap后顺序乱掉,相同数字不再在一起
        Map<Character,Boolean> map = new HashMap<Character,Boolean>();
        for(Character k:s){
            map.put(k,false);
        }
    
        // 所有孩子应是在他之后的所有元素和这个start交换后看
        int i = start;
        while(i<s.length){
            if(!map.get(s[i])) {
                map.put(s[i], true);
                //把第i个换到开头
                swap(s, start, i);
    
                backtrack(result, cur+s[start], s, start + 1,oddCnt,oddChar);
    
                //把第i个换回来
                swap(s, start, i);
            }
            ++i;
        }
    }
    
    private void swap(char[] nums,int l,int r){
        char temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
    
    private String halfToFull(String half,int oddCnt,char oddChar){
        //全偶数,直接翻转
        if(oddCnt == 0) return half + new StringBuffer(half).reverse().toString();
    
        //有奇数,最后一个不能转
        return half+oddChar + new StringBuffer(half).reverse().toString();
    }

Log in to reply
 

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