Java swap style DFS 5ms


  • 0
    C
    public class Solution {
        public List<String> generatePalindromes(String s) {
            List<String>  result = new ArrayList<>();
            StringBuilder halfSb = validPalindrome(s);
            if (halfSb == null) {
                return result;
            }
            String middle = null;
            if ((s.length() & 1) == 1) {
                middle = halfSb.substring(halfSb.length() - 1);
                halfSb.deleteCharAt(halfSb.length() - 1);
            }
            dfs(result, halfSb, 0, halfSb.length());
            recover(result, middle);
            return result;
        }
        
        private StringBuilder validPalindrome(String s) {
            if (s == null) {
                return null;
            } 
            int [] bucket = new int[256];
            for (char each : s.toCharArray()) {
                ++bucket[each];
            }
            char oddChar = '0';
            int countOdd = 0;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 256; ++i) {
                if ((bucket[i] & 1) == 1)  {
                    oddChar = (char) i;
                }            
                countOdd += (bucket[i] & 1);
                for (int j = 0; j < bucket[i] / 2; ++j) {
                    sb.append((char) i);
                }
            }
            if (countOdd == 1) {
                sb.append(oddChar);
            }
            return countOdd > 1 ? null: sb;
        }
        
        private void dfs(List<String> result, StringBuilder halfSb, int start, int end) {
            if (start == end) {
                result.add(halfSb.toString());
            }
            for (int i = start; i < end; ++i) {
                if(checkDuplicate(halfSb, start, i)) { 
                    continue;
                }
                exchange(halfSb, start, i);
                dfs(result, halfSb, start + 1, end);
                exchange(halfSb, start, i);
            }
        }
        
        private void exchange(StringBuilder halfSb, int start, int i) {
            char temp = halfSb.charAt(start);
            halfSb.setCharAt(start, halfSb.charAt(i));
            halfSb.setCharAt(i, temp);
        }
        
        private void recover(List<String> result, String middle) {
            for (int i = 0; i < result.size(); ++i) {
                String each = result.get(i);
                if (middle != null) {
                    result.set(i, each + middle + new StringBuilder(each).reverse().toString());
                } else {
                    result.set(i, each + new StringBuilder(each).reverse().toString());
                }
            }
        }
        
        private boolean checkDuplicate(StringBuilder sb, int start, int end) {
            while (start < end) {
                if (sb.charAt(start) == sb.charAt(end)) {
                    return true;
                }
                ++start;
            }
            return false;        
        }
    }
    

Log in to reply
 

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