Question: https://oj.leetcode.com/problems/palindrome-partitioning/
Question Name: Palindrome Partitioning
One simple solution is as following. It is easy to understand. And it passed all the tests.
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 | class Solution: # @param s, a string # @return a boolean def _isPalindrome(self, s): begin, end = 0, len(s)-1 while begin < end: if s[begin] != s[end]: return False else: begin += 1 end -= 1 return True # @param s, a string # @return a list of lists of string def partition(self, s): if len(s) == 0: return [] if len(s) == 1: return [[s]] result = [] if self._isPalindrome(s): result.append([s]) for i in xrange(1, len(s)): head = s[:i] if not self._isPalindrome(head): continue tailPartition = self.partition(s[i:]) result.extend([[head] + item for item in tailPartition]) return result |
We could do it better! Do it! Do it better with Manacher’s algorithm! BUT K.I.S.S.