Leetcode 132. Palindrome Partitioning II

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

Last problem is using DFS because string list is required, while in this problem, only a number is wanted, hence we can use DP.

Below p[i][j] means whether string from i to j is a palindrome, and dp[i] means how many palindromes could have under min-cut from index i to end, namely the number of cut pluses 1.

Solution:

# T:O(n^2) S:O(n^2)
class Solution:
    # @param s, a string
    # @return an integer
    # @dfs time out
    # @dp is how many palindromes in the word
    def minCut(self, s):
        dp = [0 for i in range(len(s)+1)]
        p = [[False for i in range(len(s))] for j in range(len(s))]
        for i in range(len(s)+1):
            dp[i] = len(s) - i
        for i in range(len(s)-1, -1, -1):
            for j in range(i, len(s)):
                if s[i] == s[j] and (((j - i) < 2) or p[i+1][j-1]):
                    p[i][j] = True
                    dp[i] = min(1+dp[j+1], dp[i])
        return dp[0]-1

Run Time: 764 ms