A DP Java solution with little modification to the solution of Palindrome Partitioning 1


  • 1

    Here is my solution to the previous problem Palindrome Partitioning 1.

    public static List<List<String>> partition(String s) {
        if (s.isEmpty()) return new ArrayList<>();
        int n = s.length();
        List<List<String>>[] dp = new ArrayList[n + 1];
        dp[0] = new ArrayList<>();
        dp[0].add(new ArrayList<>());
        boolean[][] isPalindrome = new boolean[n][n];
    
        for (int right = 0; right < s.length(); right++) {
            List<List<String>> res = new ArrayList<>();
            for (int left = 0; left <= right; left++) {
                if (s.charAt(left) == s.charAt(right) && (right - left <= 1 || isPalindrome[left + 1][right - 1])) {
                    isPalindrome[left][right] = true;
                    for (List l : dp[left]) {
                        ArrayList list = new ArrayList(l);
                        list.add(s.substring(left, right + 1));
                        res.add(list);
                    }
                }
            }
            dp[right + 1] = res;
        }
        return dp[n];
    }
    

    And I made a little modification so it can solve Palindrome Partitioning II.

    public static int minCut(String s) {
        if (s.isEmpty()) return 0;
        int n = s.length();
        int[] dp = new int[n];
        boolean[][] isPalindrome = new boolean[n][n];
    
        for (int right = 0; right < s.length(); right++) {
            dp[right] = right;
            isPalindrome[right][right] = true;
            for (int left = 0; left <= right; left++) {
                if (s.charAt(left) == s.charAt(right) && (right - left <= 1 || isPalindrome[left + 1][right - 1])) {
                    if (left == 0)
                        dp[right] = 0;
                    else {
                        isPalindrome[left][right] = true;
                        dp[right] = Math.min(dp[left - 1] + 1, dp[right]);
                    }
                }
            }
        }
        return dp[n - 1];
    }

Log in to reply
 

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