I got asked this question in a real life interview, I thought of just doing BFS to search for the solution. Turns out the BFS with memoization is pretty easy to code and performs well enough.

```
from collections import deque
class Solution(object):
def minCut(self, s):
"""
:type s: str
:rtype: int
"""
def is_palin(t):
return t == t[::-1]
q = deque([(len(s), 0)]) # in the form (idx to cut, # of cuts)
# keep track of which cut we are already exploring
seen = set()
while q:
pre_idx, cuts = q.popleft() . # pop left to do BFS
pre = s[:pre_idx]
if is_palin(pre):
return cuts
for i in xrange(1, len(pre)):
if i in seen: # another search already cut here
continue
post = pre[i:] # invariant is that everything in post is already palindrome
if not is_palin(post):
# if we cut at current index i, the postfix doesn't satisfy our invariant
continue
# found a place to cut where substring s[i:] can be partition into palindromes
q.append((i, cuts+1))
seen.add(i) # memoize where we are already cutting
return len(s) - 1
```