dfs java solution!


  • 0
    T
    class Solution {
        public List<String> generatePalindromes(String s) {
            char[] array = s.toCharArray();
            int[] hash = new int[256];
            for(int i=0;i<array.length;i++){
                hash[array[i]]++;
            }
            int count = 0;
            for(int i=0;i<256;i++){
                if(hash[i]%2!=0){
                    count++;
                }
                if(count>1){
                    return new ArrayList<>();
                }
            }
            
            List<String> ans = new ArrayList<>();
            solve(ans,hash,array,0,array.length-1);
            return ans;
        }
        
        public void solve(List<String> ans,int[] hash,char[] array,int left,int right){
            if(left>right){
                String str = new String(array);
                ans.add(str);
            }else{
                for(int i=0;i<256;i++){
                    if(hash[i]!=0){
                        if(left<right && hash[i]==1){
                            continue;
                        }
                        char c = (char)i;
                        array[left] = c;
                        array[right] = c;
                        
                        int count = hash[i];
                        if(left==right){
                            hash[i]--;
                        }else{
                            hash[i]-=2;
                        }
                        solve(ans,hash,array,left+1,right-1);
                        hash[i] = count;
                    }
                }
            }
        }
    }
    

Log in to reply
 

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