Java top down Backtracking solution with two pointers


  • 0
    S
    public List<String> generatePalindromes(String s) {
        List<String> res = new LinkedList<>();
        
        int[] count = new int[256];
        //mid[0] is populated if the length is odd
        int[] mid = new int[]{-1};
        
        if(!isPalindrome(s, count, mid))
            return res;
        
        dfsHelper(res, new char[s.length()], 0, s.length()-1, count, mid);
        return res;
    }
    
    //Determine if a string can be palindrome
    private boolean isPalindrome(String s, int[] count, int[] mid){
        for(int i=0; i<s.length(); i++){
            count[s.charAt(i)]++;    
        }
        
        for(int i=0; i<count.length; i++){
            if(count[i]%2==1){
                if(mid[0]==-1)
                    mid[0] = i;
                else{
                    return false;
                }
            }
        }
        
        return true;
    }
    
    //Backtracking using two pointers
    private void dfsHelper(List<String> res, char[] tmp, int left, int right, int[] count, int[] mid){
        if(left>right){
            res.add(new String(tmp));
            return;
        }else if(left==right){
            tmp[left] = (char)(mid[0]);
            res.add(new String(tmp));
            return;
        }else{
            for(int i=0; i<count.length; i++){
                if(count[i]!=0 && count[i]>=2){
                    tmp[left] = (char)(i);
                    tmp[right] = (char)(i);
                    count[i] -= 2;
                    dfsHelper(res, tmp, left+1, right-1, count, mid);
                    count[i] += 2;
                }
            }
        }
    }

Log in to reply
 

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