<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:
    bool isPalindrome(int i, int k, string& s) {
        while (i <= k) {
            if (s[i] != s[k]) {
                return false;
            }
            i++;
            k--;
        }
        return true;
    }
    // Brute force: Cut or not cut an every single point.
    // Time complexity: O(2^n)
    // vector<vector<string_view>> solve(int i, string& s) {
    //     if (i >= s.size()) {
    //         return {};
    //     }

    //     vector<vector<string_view>> result;
    //     for (int k = i; k < s.size(); ++k) {
    //         if (!isPalindrome(i, k, s)) {
    //             continue;
    //         }
    //         string_view current = string_view(&s[i], k - i + 1);
    //         if (k == s.size() - 1) {
    //             result.push_back({current});
    //             continue;
    //         }
    //         vector<vector<string_view>> local_result = solve(k + 1, s);
    //         if (local_result.empty()) {
    //             continue;
    //         }
    //         for (vector<string_view>& local : local_result) {
    //             local.insert(local.begin(), current);
    //         }
    //         result.insert(result.end(), local_result.begin(),
    //                       local_result.end());
    //     }
    //     return result;
    // }
    // vector<vector<string>> partition(string s) {
    //     vector<vector<string_view>> result = solve(0, s);
    //     vector<vector<string>> transform(result.size());
    //     for (int i = 0; i < result.size(); ++i) {
    //         vector<string> r(result[i].size());
    //         for (int j = 0; j < result[i].size(); ++j) {
    //             r[j] = string(result[i][j]);
    //         }
    //         transform[i] = r;
    //     }
    //     return transform;
    // }

    vector<vector<string>> partition(string s) {
        vector<vector<vector<string_view>>> dp(s.size() + 1);
        for (int i = s.size() - 1; i >= 0; --i) {
            vector<vector<string_view>> result;
            for (int k = i; k < s.size(); ++k) {
                if (!isPalindrome(i, k, s)) {
                    continue;
                }
                string_view current = string_view(&s[i], k - i + 1);
                if (k == s.size() - 1) {
                    result.push_back({current});
                    continue;
                }
                vector<vector<string_view>> local_result = dp[k + 1];
                if (local_result.empty()) {
                    continue;
                }
                for (vector<string_view>& local : local_result) {
                    local.insert(local.begin(), current);
                }
                result.insert(result.end(), local_result.begin(),
                              local_result.end());
            }
            dp[i] = result;
        }
        vector<vector<string_view>> result = dp[0];

        vector<vector<string>> transform(result.size());
        for (int i = 0; i < result.size(); ++i) {
            vector<string> r(result[i].size());
            for (int j = 0; j < result[i].size(); ++j) {
                r[j] = string(result[i][j]);
            }
            transform[i] = r;
        }
        return transform;
    }
};
222164