131. Palindrome Partitioning Medium

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

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

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

Approach

Input: A string s

Output: Partition s into several substrings, ensuring every substring is a palindrome, returning all valid partitioning approaches.

This problem belongs to Partition Backtracking (subset backtracking) problems.

• We can scan from left to right, trying to partition the string at every possible position.
• After each cut, we take the left part and check if it's a palindrome string.
• If it is, we add it to the current partitioning scheme (put into path).
• Then we continue recursively processing the remaining part.
• If we reach the end of the string, it means we found a valid entire partitioning scheme, and we save it to the answer (put into ans).

Three Questions of Backtracking

1. Current Operation?

   • At the current position i, try to extract a substring t from s[i:j+1].
   • Check if this substring t is a palindrome. If so, add it to the path path.
   • Which means putting the valid palindrome substring into the path, representing "I have chosen this partitioned piece".

2. Sub-problem?

   • After choosing the palindrome substring t, we need to continue recursively processing the remaining string.
   • That means starting from position j+1, continue partitioning the remaining substring.

3. Next Sub-problem?

   • The next recursion is dfs(j+1), signifying partitioning the remaining string from j+1.
   • Continue downwards to construct all possible partitioning paths.

Pruning Conditions

• Only when s[i:j+1] is a palindrome string, we append it to the path and recurse to partition further. If it is not a palindrome, we simply skip it and do not recurse.

Implementation

python

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        ans = []   # Final result, storing all partitioning schemes
        path = []  # The current partitioning path
        n = len(s) # Length of the string

        def dfs(i):
            # If we've traversed right to the string's end, save current path format into ans
            if i == n:
                ans.append(path.copy())
                return

            # Enumerate all possible partitioning cut positions
            for j in range(i, n):
                t = s[i:j+1]  # Extract substring s[i..j]

                # Check whether substring checks out as palindrome
                if t == t[::-1]:
                    path.append(t)    # If it is, slot into path
                    dfs(j + 1)        # Deep dive into partitioning remaining string array
                    path.pop()        # Backtrack, removing last substring slice

        dfs(0)  # Launch recursion from index 0
        return ans

javascript

/**
 * @param {string} s
 * @return {string[][]}
 */
const partition = function(s) {
    const ans = [];
    const path = [];

    function dfs(i) {
        if (i == s.length) {
            ans.push([...path]);
            return;
        }

        for (let j = i; j < s.length; j++) {
            const sub = s.slice(i, j + 1);
            const backSub = sub.split('').reverse().join('');

            if (sub == backSub) {
                path.push(sub);
                dfs(j + 1);
                path.pop();
            }
        }
    }
    dfs(0);
    return ans;
};

Complexity Analysis

• Time Complexity: O(n * 2^n)
• Space Complexity: O(n * 2^n)

Links

131. Palindrome Partitioning (English)

131. 分割回文串 (Chinese)