def minCut_MLE(self, s):
        q = [[s]]
        count = -1
        while q:
            # cur = q.pop(0)  # not directly pop
            length = len(q)
            count += 1
            for cur_level in xrange(length):
                cur = q[cur_level]
                if all(self.is_palindrome(item) for item in cur):
                    return count
                # 1 cut
                for ind, val in enumerate(cur):
                    for i in xrange(1, len(val)):
                        cut1 = val[:i]
                        cut2 = val[i:]
                        new_cur = list(cur)
                        new_cur[ind] = cut1
                        new_cur.insert(ind+1, cut2)
                        q.append(new_cur)
            q = q[length:]
bfs
dataset/ETHPy150Open algorhythms/LeetCode/132 Palindrome Partitioning II.py/Solution.minCut_MLE