Palindrome Partitioning II.

Vinay
Nov 18, 2018

--

It’s better to use 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.

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++;
}
}

--

--

Vinay
Vinay

No responses yet