[leetcode]Palindrome Partitioning @ Python

原题地址：https://oj.leetcode.com/problems/palindrome-partitioning/

题意：

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [

    ["aa","b"],

    ["a","a","b"]

  ]

解题思路：回文的分割问题。同样是需要穷举出所有符合条件的集合，那么我们还是使用dfs。

代码：

class Solution:

    # @param s, a string

    # @return a list of lists of string

    def isPalindrome(self, s):

        for i in range(len(s)):

            if s[i] != s[len(s)-1-i]: return False

        return True

    def dfs(self, s, stringlist):

        if len(s) == 0: Solution.res.append(stringlist)

        for i in range(1, len(s)+1):

            if self.isPalindrome(s[:i]):

                self.dfs(s[i:], stringlist+[s[:i]])

    def partition(self, s):

        Solution.res = []

        self.dfs(s, [])

        return Solution.res

巴特西

[leetcode]Palindrome Partitioning @ Python

最新文章

热门文章