Java solution beats 96% using customized charArray


  • 0
    G
    public List<String> generatePalindromes(String s) {
            List<String> res = new ArrayList<>();
            char[] input = s.toCharArray();
            Arrays.sort(input);
            String odd = "";
            int i = 0, j = 0;
            // init input
            while(i < input.length){
                if(i == input.length - 1 || input[i] != input[i+1]){
                    if(odd.equals("")){
                        odd += input[i];
                        i++;
                    }
                    // no palindrome
                    else return res;
                }
                else {
                    input[j++] = input[i];
                    i += 2;
                }
            }
            StringBuilder sb = new StringBuilder();
            boolean[] visit = new boolean[j];
            backtracking(res, sb, input, visit, j, odd);
            return res;
        }
        
        private void backtracking(List<String> res, StringBuilder sb, char[] input, boolean[] visit, int size, String odd){
            if(sb.length() == size){
                res.add(sb.reverse().toString() + odd + sb.reverse().toString());
                return;
            }
            for(int i = 0; i < size; i++){
                if(visit[i]) continue;
                visit[i] = true;
                sb.append(input[i]);
                backtracking(res, sb, input, visit, size, odd);
                visit[i] = false;
                sb.deleteCharAt(sb.length() - 1);
                while(i + 1 < size && input[i] == input[i+1]) i++;
            }
        }
    

  • 0
    S

    @Guyuelulin I dont know why it is "res.add(sb.reverse().toString() + odd + sb.reverse().toString());" rather than "res.add(sb.toString() + odd + sb.reverse().toString());". Could you explain it a bit? I know your answer is correct and I just dont know why, thank you.


Log in to reply
 

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