My Java Double DP solution


  • 0
    M
        public List<List<String>> partition(String s) {
            List<List<String>> lists = new ArrayList<>();
            if (s == null || s.length() == 0) return lists;
            int n = s.length();
            boolean[][] isPal = new boolean[n][n];
            for (int len = 1; len <= n; ++len) {
                for (int i = 0; i + len - 1 < n; ++i) {
                    int j = i + len - 1;
                    if (len == 1) isPal[i][j] = true;
                    else if (len == 2) isPal[i][j] = s.charAt(i) == s.charAt(j);
                    else isPal[i][j] = s.charAt(i) == s.charAt(j) && isPal[i + 1][j - 1];
                }
            }
            List<List<List<String>>> ans = new ArrayList<>(n);
            
            for (int i = 0; i < n; ++i) {
                ans.add(new ArrayList<>());
                if (isPal[0][i]) {
                    List<String> list = new ArrayList<>();
                    list.add(s.substring(0, i + 1));
                    ans.get(i).add(list);
                }
                for (int j = 1; j <= i; ++j) {
                    if (isPal[j][i]) {
                        for (List<String> pre : ans.get(j - 1)) {
                            List<String> list = new ArrayList<>(pre);
                            list.add(s.substring(j, i + 1));
                            ans.get(i).add(list);
                        }
                    }
                }
            }
            return ans.get(n - 1);
        }
    

Log in to reply
 

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