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
```