aboutsummaryrefslogtreecommitdiff
path: root/palindrome_partitioning.py
diff options
context:
space:
mode:
Diffstat (limited to 'palindrome_partitioning.py')
-rw-r--r--palindrome_partitioning.py35
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"))