A different way to solve with AC Java code. Feels there is room to improve, please advise


  • 0
    T

    The idea was to get all the Palindrome in the String and store the information. I stored each Palindrome as a key value pair in a map. Left end will be the key and the value is the list of possible right end. The way I explore the Palindromes made sure the right ends are added in increasing order. Used DFS to get the result. Saved already resolved results. Still, feels like this solution can be improved for the DFS part. Please advise.

        public List<List<String>> partition(String s) {
            Map<Integer, List<Integer>> map = new HashMap<>();
            char[] S = s.toCharArray();
            int l, r;
            for (int i = 0; i < S.length; i++) {
                map.put(i, new LinkedList<>(Arrays.asList(i)));
                l = i;
                r = i + 1;
                while (l >= 0 && r < S.length && S[l] == S[r]) {
                    if (map.containsKey(l)) {
                        map.get(l).add(r);
                    }
                    l--;
                    r++;
                }
                l = i - 1;
                r = i + 1;
                while (l >= 0 && r < S.length && S[l] == S[r]) {
                    if (map.containsKey(l)) {
                        map.get(l).add(r);
                    }
                    l--;
                    r++;
                }
            }
            Map<Integer, List<List<String>>> resolved = new HashMap<>();
            return partition(s, map, resolved, 0);
        }
        public List<List<String>> partition(String s, Map<Integer, List<Integer>> map, Map<Integer, List<List<String>>> resolved, int start) {
            if (resolved.containsKey(start)) {
                return resolved.get(start);
            }
            List<List<String>> res = new LinkedList<>();
            for (int end : map.get(start)) {
                String str = s.substring(start, end+1);
                if (end + 1 == s.length()) {
                    List<String> list = new LinkedList<>();
                    list.add(str);
                    res.add(list);
                    resolved.put(start, res);
                    return res;
                }
                for (List<String> list : partition(s, map, resolved, end+1)) {
                    List<String> tmp = new LinkedList<>(list);
                    
                    tmp.add(0, str);
                    res.add(tmp);
                }
            }
            resolved.put(start, res);
            return res;
        }
    

Log in to reply
 

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