Palindrome Partitioning II.

I was thinking for some days about this problem if i can solve in O(n). I still think there must be better than O(n²) algorithm, couldn’t come up with one. Then i decided to start solve in O(n²).

I used expand around concept to find all palindrome strings centered at given point. This would take O(n²) time. when expanding, find update both sides' optimal palindrome partition cut. which will give us optimal solution for the whole string.

I quickly checked other algorithms, they look ridiculously complex and most of them were not original answers and explanation lacked why they have to be the way they are.

public int minCut(String s) {
        int n = s.length();
        char[] t = s.toCharArray();
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = -1;
        int i = 0;
        while(i < n) {
            expandAround(t, i, i, dp);
            expandAround(t, i, i+1, dp);
            i++;
        }
        return dp[n];
    }
    
    public void expandAround(char[] t, int i , int j, int[] dp) {
        while(i >= 0 && j < t.length && t[i] == t[j]) {
            dp[j+1] = Math.min(dp[j+1], dp[i]+1);
            i--;j++;
        }
    }