0132. Palindrome Partitioning II

https://leetcode.com/problems/palindrome-partitioning-ii

Description

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example 1:

**Input:** s = "aab"
**Output:** 1
**Explanation:** The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:

**Input:** s = "a"
**Output:** 0

Example 3:

**Input:** s = "ab"
**Output:** 1

Constraints:

• 1 <= s.length <= 2000

• s consists of lower-case English letters only.

ac

class Solution {
    public int minCut(String s) {
        // edge cases
        if (s == null || s.length() <= 1) return 0;

        int n = s.length();
        int[] dp = new int[n];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = i;
        }

        for (int i = 0; i < n; i++) {
            // 1st round, aba
            int l = i, r = i;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                int tmp = l == 0 ? 0 : dp[l-1] + 1; // if l reach head, 0 cut.
                dp[r] = Math.min(dp[r], tmp);
                l--;
                r++;
            }

            // 2nd round, abba
            l = i; r = i + 1;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                int tmp = l == 0 ? 0 : dp[l-1] + 1; // if l reach head, 0 cut.
                dp[r] = Math.min(dp[r], tmp);
                l--;
                r++;
            }
        }

        return dp[n-1];
    }
}