2ms solution. Can anyone help me to simplify my code? Much appreciated


  • 0
    X
    public class Solution {
    private List<String> result;
    private boolean[] marked;
    
    public List<String> generatePalindromes(String s) {
        result = new ArrayList<>();
    
        int N = s.length();
        boolean hasOdd = false;
        int oddChar = Integer.MIN_VALUE;
        int[] asciiTable = new int[256];
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < N; i++)
            ++asciiTable[s.charAt(i)];
        
        for (int i = 0; i < 256; i++) {
            if (asciiTable[i] > 0) {
                int times = asciiTable[i] / 2;
                
                for (int j = 0; j < times; j++)
                    sb.append((char) i);
    
                if (asciiTable[i] % 2 == 1) {
                    if (!hasOdd) {
                        hasOdd = true;
                        oddChar = i;
                    } else {
                        return result;
                    }
                }
            }
        }
        
        marked = new boolean[sb.length()];
        char[] charArray = sb.toString().toCharArray();
        generatePalindromesHelper(charArray, new StringBuilder(), hasOdd, oddChar);
        
        return result;
    }
    
    private void generatePalindromesHelper(char[] charArray, StringBuilder sb, boolean hasOdd, int oddChar) {
        if (sb.length() == charArray.length) {
            String leftHalf = sb.toString();
            int M = leftHalf.length();
            StringBuilder palindrome = new StringBuilder();
            
            for (int i = 0; i < M; i++)
                palindrome.append(leftHalf.charAt(i));
            
            if (hasOdd)
                palindrome.append((char) oddChar);
            
            for (int i = M - 1; i >= 0; i--)
                palindrome.append(leftHalf.charAt(i));
            
            result.add(palindrome.toString());
        }
        
        for (int i = 0; i < charArray.length; i++) {
            if (i > 0 && !marked[i - 1] && charArray[i - 1] == charArray[i])
                continue;
            
            if (!marked[i]) {
                sb.append(charArray[i]);
                marked[i] = true;
                generatePalindromesHelper(charArray, sb, hasOdd, oddChar);
                sb.deleteCharAt(sb.length() - 1);
                marked[i] = false;
            }
        }       
    }
    

    }


Log in to reply
 

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