leetcode

Palindrome Partitioning

Palindrome Partitioning

DFS Version - 192ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        res = []
        self.dfs(s, [], res)
        return res
    def dfs(self, s, path, res):
        if not s:
            res.append(path)
            return
        for i in range(1, len(s) + 1):
            if self.is_palindrome(s[:i]):
                self.dfs(s[i:], path + [s[:i]], res)
    def is_palindrome(self, s):
        return s == s[::-1]

test code

1
2
In [10]: s = Solution(); t = s.partition("aab"); print(t)
[['a', 'a', 'b'], ['aa', 'b']]

leet code