Simple Java solution without using boolean array


  • 0
    public class Solution {
    	public List<String> generatePalindromes(String s) {
    		Map<Character, Integer> map = new HashMap<>();
    		boolean hasOdd = false;
    
    		List<String> res = new ArrayList<>();
    		for (char chr : s.toCharArray()) {
    			map.put(chr, map.containsKey(chr) ? map.get(chr) + 1 : 1);
    		}
    
    		List<Character> list = new ArrayList<>();
    		String mid = "";
    		for (char chr : map.keySet()) {
    			if (map.get(chr) % 2 != 0) {
    				if (hasOdd) {
    					return res;
    				}
    				hasOdd = true;
    				mid = String.valueOf(chr);
    				map.put(chr, map.get(chr) - 1);
    			}
    			for (int i = 0; i < map.get(chr) / 2; i++) {
    				list.add(chr);
    			}
    		}
    
    		search(new StringBuilder(), mid, list, res);
    		return res;
    	}
    
    	private void search(StringBuilder prefix, String mid, List<Character> list, List<String> res) {
    		if (list.isEmpty()) {
    			res.add(prefix.toString() + mid + prefix.reverse().toString());
    			prefix.reverse();
    			return;
    		}
    
    		for (int i = 0; i < list.size(); i++) {
    			char chr = list.get(i);
    			if (i > 0 && list.get(i - 1) == list.get(i))
    				continue;
    			prefix.append(chr);
    			list.remove(i);
    			search(prefix, mid, list, res);
    			list.add(i, chr);
    			prefix.deleteCharAt(prefix.length() - 1);
    		}
    	}
    
    }
    
    

Log in to reply
 

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