Question: https://oj.leetcode.com/problems/palindrome-partitioning-ii/
Question Name: Palindrome Partitioning II
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | class Solution: # @param s, s string # @return an array def _buildPalindromeCache(self, s): ''' http://en.wikipedia.org/wiki/Longest_palindromic_substring Method: Manacher's algorithm ''' 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 self._isPalindrome(0, index, palindromeCache): # 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 self._isPalindrome(tryingToCut, index, palindromeCache): minCut = min(minCut, 1 + minCutEndingHere[tryingToCut-1]) minCutEndingHere[index] = minCut return minCutEndingHere[-1] |