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.

A palindrome string is a string that reads the same backward as forward.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

• 1 <= s.length <= 16
• s contains only lowercase English letters.

SOLUTION:

class Solution:
    def isPalindrome(self, s, i, j):
        if i >= j - 1:
            return s[i] == s[j - 1]
        if s[i] == s[j - 1]:
            return self.isPalindrome(s, i + 1, j - 1)
        return False

    def getPos(self, s, i, n):
        if i == n:
            return [[]]
        op = []
        for j in range(i + 1, n + 1):
            if self.isPalindrome(s, i, j):
                curr = s[i:j]
                val = self.getPos(s, j, n)
                op += [[curr] + v for v in val]
        return op

    def partition(self, s: str) -> List[List[str]]:
        return self.getPos(s, 0, len(s))