<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 {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        std::unordered_map<int, std::vector<std::vector<std::string>>> dp{};
        dp[n] = {{}};
        fn(s, dp, 0);
        return dp[0];
    }
    void fn(std::string const& s,
            std::unordered_map<int, std::vector<std::vector<std::string>>>& dp,
            int idx) {
        if (idx == s.size() || dp.find(idx) != dp.end()) {
            return;
        }
        auto& res = dp[idx];
        for (int len = 1; idx + len <= s.size(); ++len) {
            if (isPalindrome(s, idx, idx + len - 1)) {
                fn(s, dp, idx + len);
                auto sstr = s.substr(idx, len);
                for (auto const& vals : dp[idx + len]) {
                    res.push_back({});
                    res.back().push_back(sstr);
                    for (auto const& val : vals) {
                        res.back().push_back(val);
                    }
                }
            }
        }
        return;
    }
    bool isPalindrome(std::string_view sv, int first, int last) {
        while (first < last) {
            if (sv[first] != sv[last]) {
                return false;
            }
            ++first;
            --last;
        }
        return true;
    }
};
183929