This is a shortest path problem.


  • 1
    Y

    Find every palindrome substring, then this problem turns out to be a shortest path problem.

    from collections import deque
    class Solution:
        # @param s, a string
        # @return an integer
        def minCut(self, s):
            #if j in palindrome[i], then s[i:j] is a palindrome
            palindrome=[{i+1} for i in range(len(s))]
            for i in range(len(s)):
                j=1
                while i>=j and i+j <len(s) and s[i-j]==s[i+j]:
                    palindrome[i-j].add(i+j+1)
                    j+=1
                j=0
                while i>=j and i+j+1<len(s) and s[i-j]==s[i+j+1]:
                    palindrome[i-j].add(i+j+2)
                    j+=1
            cut=0
            visited=set([0])
            q=deque()
            q.append((0,0))
            while q:
                i,cut=q.popleft()
                for j in palindrome[i]:
                    if j==len(s):
                        return cut
                    if j not in visited:
                        q.append((j,cut+1))
                        visited.add(j)
            return cut

Log in to reply
 

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