Java easy to understand recursive solution.


  • 0
    C
    public List<String> generatePalindromes(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (char c: s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0)+1);
        }
        int count = 0;
        String mid = "";
        List<Character> half = new ArrayList<>();
        for (Map.Entry<Character, Integer> entry: map.entrySet()) {
            if (entry.getValue()%2==1) {
                count++;
                mid = entry.getKey().toString();
            } 
            for (int i = 0; i < entry.getValue()/2; i++) {
                half.add(entry.getKey());
            }
        }
        if (count > 1) {  // more than one "odd" Character
            return new ArrayList<>();
        }
        Collections.sort(half);
        List<String> ret = new ArrayList<>();
        boolean[] visited = new boolean[half.size()];
        dfs(half, mid, visited, "", ret);
        return ret;
    }
    
    private void dfs(List<Character> half, String mid, boolean[] visited, String path, List<String> ret) {
        if (path.length() == half.size()) {
            String s = path + mid + new StringBuilder(path).reverse().toString();
            ret.add(s);
        }
        for (int i = 0; i < half.size(); i++) {
            if (visited[i] || (i > 0 && half.get(i).equals(half.get(i-1)) && !visited[i-1])) {
                continue;
            }
            visited[i] = true;
            dfs(half, mid, visited, path+half.get(i), ret);
            visited[i] = false;
        }
    }

Log in to reply
 

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