<p>Given a string <code>s</code>, partition <code>s</code> such that every <span data-keyword="substring-nonempty">substring</span> of the partition is a <span data-keyword="palindrome-string"><strong>palindrome</strong></span>. Return <em>all possible palindrome partitioning of </em><code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "aab"
<strong>Output:</strong> [["a","a","b"],["aa","b"]]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "a"
<strong>Output:</strong> [["a"]]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 16</code></li>
	<li><code>s</code> contains only lowercase English letters.</li>
</ul>

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        sol = list()
        #find all palindromes in string
        paliDict = {}

        #paliDict[startIdx] = [(endIdx, palindrome)]
        for i in range(len(s)-1):
            # find palindromes from middle
            # even
            lhs = i
            rhs = i
            palindrome = ""
            while lhs >= 0 and rhs < len(s) and s[lhs] == s[rhs]:
                newChar = s[lhs]
                if len(palindrome) == 0:
                    palindrome = newChar
                    paliDict[lhs] = [(lhs + 1, palindrome)]
                else:
                    palindrome = newChar + palindrome + newChar
                    paliDict[lhs].append((rhs + 1, palindrome))
                lhs -= 1
                rhs += 1
            # odd
            lhs = i
            rhs = i + 1
            palindrome = ""
            while lhs >= 0 and rhs < len(s) and s[lhs] == s[rhs]:
                newChar = s[lhs]
                palindrome = newChar + palindrome + newChar
                paliDict[lhs].append((rhs + 1, palindrome))
                lhs -= 1
                rhs += 1

        lastIdx = len(s) - 1
        paliDict[lastIdx] = [(len(s), s[lastIdx])]

        #find all combinations of ranges
        sol = list()
        self.helper(sol, paliDict, s, 0, list())
        return sol

    def helper(self, sol, paliDict, s, currIdx, combo):
        if currIdx == len(s):
            sol.append(combo)
            return
        for elem in paliDict[currIdx]:
            endIdx = elem[0]
            currPalindrome = elem[1]
            comboCopy = combo.copy()
            comboCopy.append(currPalindrome)
            self.helper(sol, paliDict, s, endIdx, comboCopy)
25143