AC Java Solution Backtracking with HashSet and Map


  • 0
    A

    The Procedure:

    1. Using HashSet to determine if the input is capable of being a palindrome.
    2. Using HashMap to store the frequency of every character. If the length of input is odd, add the extra character to StringBuilder first, at the same time subtract 1 of the very character frequency.
    3. Backtracking the map, add one character to both head and tail of StringBuilder, subtracting 2 of the very character frequency.
    public class Solution {
        public List<String> generatePalindromes(String s) {
            List<String> result = new ArrayList<String>();
            Set<Character> set = new HashSet<Character>();
            Map<Character, Integer> frequency = new HashMap<Character, Integer>();
            for (char ch : s.toCharArray()) {
                if (set.contains(ch)) set.remove(ch);
                else set.add(ch);
                if (frequency.containsKey(ch)) frequency.put(ch, frequency.get(ch) + 1);
                else frequency.put(ch, 1);
            }
            StringBuilder palin = new StringBuilder();
            //determine if the input is capable of being a palindrome
            if (set.size() > 1) return result;
            else if (set.size() == 1) {
                char ch = set.iterator().next();
                palin.append(ch);
                frequency.put(ch, frequency.get(ch) - 1);
            }
            generate(frequency, s.length(), palin, result);
            return result;
        }
        private void generate(Map<Character, Integer> frequency, int len, StringBuilder palin, List<String> result) {
            if (palin.length() == len) {
                result.add(palin.toString());
                return;
            }
            for (Map.Entry<Character, Integer> entry : frequency.entrySet()) {
                if (entry.getValue() == 0) continue;
                StringBuilder temp = new StringBuilder(palin.toString());
                temp.insert(0, entry.getKey());
                temp.append(entry.getKey());
                frequency.put(entry.getKey(), entry.getValue() - 2);
                generate(frequency, len, temp, result);
                frequency.put(entry.getKey(), entry.getValue() + 2);
            }
        }
    }
    

Log in to reply
 

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