[java/6ms] using extra array to memorize, avoiding overlapping cases


  • 0

    List<List<String>> map[] = new ArrayList[s.length()+1];
    This code may works fine for string like this "aaaaaaaaaaaaaaaaaaaaaaaaaaaaab"

    public List<List<String>> partition(String s) {
            if (s == null || s.length() == 0)
                return new ArrayList<>();
    
            List<List<String>> map[] = new ArrayList[s.length()+1];
            List<String> co = new ArrayList<>();
            for (int i = s.length()-1; i >= 0; i--) {
                List<List<String>> res = new ArrayList<>();
                partition(s, i, res, co, map);
                map[i] = res;
            }
    
            return map[0];
        }
    
        private void partition(String s, int start, List<List<String>> res, List<String> combination, List<List<String>> map[]) {
            if (start == s.length()) {
                res.add(new ArrayList<>(combination));
                return;
            }
            char ch = s.charAt(start);
            for (int i = s.length()-1; i >= start; i--) {
                if (s.charAt(i) == ch) {
                    if (this.isPalindrome(s, start+1, i-1)) {
                        combination.add(s.substring(start, i+1));
                        List<List<String>> prev = map[i+1];
                        if (prev == null)
                            partition(s, i+1, res, combination, map);
                        else {
                            for (List<String> lst : prev) {
                                List<String> tmp = new ArrayList<>(combination);
                                tmp.addAll(lst);
                                res.add(tmp);
                            }
                        }
                        combination.remove(combination.size()-1);
                    }
                }
            }
        }
    
        private boolean isPalindrome(String s, int start, int end) {
            int i = start, j = end;
            while (i < j) {
                if (s.charAt(i) == s.charAt(j)) {
                    i++;
                    j--;
                } else {
                    break;
                }
            }
            return i >= j;
        }
    

Log in to reply
 

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