diff options
Diffstat (limited to 'palindrome_partitioning.py')
-rw-r--r-- | palindrome_partitioning.py | 35 |
1 files changed, 35 insertions, 0 deletions
diff --git a/palindrome_partitioning.py b/palindrome_partitioning.py new file mode 100644 index 0000000..32805e8 --- /dev/null +++ b/palindrome_partitioning.py @@ -0,0 +1,35 @@ +# 131. Palindrome Partitioning +from collections import defaultdict + +""" +given: string 's', parition 's' such that every substring of the parition +is a palindrome. return all possible palindrome paritioning of 's'. +""" + + +class Solution(object): + def __init__(self): + self.memory = defaultdict(list) + + def partition(self, s): + """ + :type s: str + :rtype: List[List[str]] + """ + if not s: + return [[]] + if s in self.memory: + return self.memory[s] + ans = [] + for i in range(1, len(s) + 1): + if s[:i] == s[:i][::-1]: + for suf in self.partition(s[i:]): + ans.append([s[:i]] + suf) + self.memory[s] = ans + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.partition(s="aab")) + print(obj.partition(s="a")) |