Leetcode: Palindrome Partitioning II @Python

Use Manacher's algorithm with O(n) O(n^2) Dynamic Programming is not optimal. My Manacher's algorithm implementation got TLE. I learn from the solution here.

class Solution:
    # @param s, s string
    # @return an array
    def _buildPalindromeCache(self, s):
        transformed = "#" + "#".join(s) + "#"
        palindrome_len = [1] * len(transformed)
        
        center = 0
        farest = 0
        
        for index in xrange(1, len(transformed)):
            if farest <= index:
                tryingLen = 1
            else:
                preComputedLen = palindrome_len[2*center-index]
                if preComputedLen + index > farest:
                    tryingLen = farest + 1 - index
                else:
                    palindrome_len[index] = preComputedLen
                    continue
            
            while index + tryingLen < len(transformed) and \
                  index - tryingLen >= 0:
                if transformed[index + tryingLen] == \
                   transformed[index - tryingLen]:
                    tryingLen += 1
                else:
                    break
            
            if index + tryingLen -1 > farest:
                farest = index + tryingLen -1
                center = index
            
            palindrome_len[index] = tryingLen
        
        return palindrome_len
 
    # @param begin, an integer
    # @param end, an integer
    # @param palindromeCache, an array
    # @return a boolean
    #def _isPalindrome(self, begin, end, palindromeCache):
        ''' In palindromeCache, the index for s[index] and s[end] are
            index*2+1 and end*2+1 respectively. So in palindromeCache, the
            middle point of s[index] and s[end] is (index*2+1 + end*2+1) // 2,
            that is (index + end + 1).
            IF you remove this function and use a single statement instead, you
            could get a 30%-40% performance improvement or even more.
        '''
       # return palindromeCache[begin + end + 1] - 1 >= (end - begin + 1)
    
    # @param s, a string
    # @return an integer
    def minCut(self, s):
        ''' Solve it in a dynamic programming method.
        '''
        if len(s) == 0:     return 0
 
        palindromeCache = self._buildPalindromeCache(s)
        minCutEndingHere = [0] * len(s)
        
        for index in xrange(1, len(s)):            
            if palindromeCache[index + 1] - 1 >= (index + 1):
                # The substring from beginning to here is a palindrome. No
                # cut is needed.
                minCut = 0
            else:
                # We could add a cut between index and index - 1.
                minCut = 1 + minCutEndingHere[index-1]
                
                # Or the cut could be tried between tryingToCut and 
                # tryingToCut - 1.
                for tryingToCut in xrange(1, index):
                    # Only when s[tryingToCut : index+1] is palindrome, the
                    # cut could be done.
                    if palindromeCache[tryingToCut + index + 1] - 1 >= (index - tryingToCut + 1):
                        minCut = min(minCut, \
                                     1 + minCutEndingHere[tryingToCut-1])
                    
            minCutEndingHere[index] = minCut
        
        return minCutEndingHere[-1]