Question

Formatted question description: https://leetcode.ca/all/131.html

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"]]

Constraints:

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

Algorithm

It employs dynamic programming (DP) to identify all substrings that are palindromes and then uses depth-first search (DFS) to explore all possible partitioning combinations that consist exclusively of palindrome substrings.

Dynamic Programming (DP) Phase

Initialization: A 2D list dp of size n x n is created, where n is the length of the input string s. Each element dp[i][j] indicates whether the substring s[i:j+1] is a palindrome.
DP Logic: The code fills the dp table in reverse order (starting from the end of the string and moving towards the beginning). This reverse order ensures that when checking if s[i:j+1] is a palindrome (and s[i] == s[j]), the result of the inner substring s[i+1:j] is already calculated and stored in dp[i+1][j-1].
Palindrome Conditions: A substring s[i:j+1] is considered a palindrome if the start and end characters are equal (s[i] == s[j]) and either of the following conditions is true:
- The substring’s length is 2 or less (abs(i - j) <= 1), meaning it’s either a single character or two identical characters.
- The inner substring s[i+1:j] is a palindrome (dp[i+1][j-1] is True).

Depth-First Search (DFS) Phase

Recursive DFS Function: The function dfs recursively explores all possible ways to partition the string s starting from index i into palindrome substrings. It accumulates partitions in a temporary list t and adds a copy of t to the final answer ans when it reaches the end of the string.
DFS Logic: For each position i in the string, the function iterates over all possible end indices j (from i to n-1). If the substring s[i:j+1] is a palindrome (dp[i][j] is True), it adds this substring to the current partition t and recurses to the next position j+1. After exploring all partitions starting with s[i:j+1], it removes the last added substring from t to backtrack and explore other possibilities.
Base Case: When i equals the length of the string (n), it means a valid partitioning of s into palindrome substrings is found, and a copy of the current partition t is added to ans.

Final Output

The solution initiates the DFS search with dfs(s, 0, []), starting from the beginning of the string and an empty partition list. After exploring all possible partitioning, it returns ans, which contains all the valid palindrome partitioning of s.

This approach smartly combines dynamic programming to efficiently identify palindromes within the string and depth-first search to explore all partitioning possibilities, ensuring a comprehensive solution to the palindrome partitioning problem.

Code

import java.util.ArrayList;
import java.util.List;

public class Palindrome_Partitioning {

    public class Solution_dp {

        public List<List<String>> partition(String s) {

            int n = s.length();
            List<List<String>> res = new ArrayList<>();
            List<String> out = new ArrayList<>();
            boolean[][] dp = new boolean[n][n];
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j <= i; ++j) {
                    if (s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j + 1][i - 1])) {
                        dp[j][i] = true;
                    }
                }
            }

            helper(s, 0, dp, out, res);
            return res;
        }

        void helper(String s, int start, boolean[][] dp, List<String> out, List<List<String>> res) {
            if (start == s.length()) {
                res.add(new ArrayList<>(out));
                return;
            }
            for (int i = start; i < s.length(); ++i) {
                if (!dp[start][i]) continue;

                out.add(s.substring(start, i + 1));
                helper(s, i + 1, dp, out, res);
                out.remove(out.size() - 1);
            }
        }
    }

    // based on part-I, just count each partition to find min...
    public class Solution_over_time {
        List<List<String>> list = new ArrayList<>();

        public List<List<String>> partition(String s) {

            if (s == null || s.length() == 0) {
                return list;
            }

            find(s, new ArrayList<String>());

            return list;
        }

        private void find(String s, ArrayList<String> currentList) {

            if (s.length() == 0) {
                list.add(currentList);

                return;
            }

            // idea is, scan from index=0, to find each palindrome, then rest substring to next recursion
            for (int i = 0; i < s.length(); i++) {

                String sub = s.substring(0, i + 1); // @note: substring 0-s[i]
                // System.out.println("substring is: " + sub);

                if (isPal(sub)) {

                    ArrayList<String> nextList = new ArrayList<>(currentList); // deep copy
                    nextList.add(sub);
                    find(s.substring(i + 1), nextList);
                }
            }

        }

        private boolean isPal(String s) {
            int i = 0;
            int j = s.length() - 1;

            while (i <= j) {

                // @note: better in if (s.charAt(i++) != s.charAt(j--)) { // @note: 忘了这里的++和--。。。
                if (s.charAt(i) != s.charAt(j)) {
                    return false;
                }

                i++;
                j--;

            }

            return true;
        }
    }

}

############

class Solution {
    private boolean[][] dp;
    private List<List<String>> ans;
    private int n;

    public List<List<String>> partition(String s) {
        ans = new ArrayList<>();
        n = s.length();
        dp = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(dp[i], true);
        }
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
            }
        }
        dfs(s, 0, new ArrayList<>());
        return ans;
    }

    private void dfs(String s, int i, List<String> t) {
        if (i == n) {
            ans.add(new ArrayList<>(t));
            return;
        }
        for (int j = i; j < n; ++j) {
            if (dp[i][j]) {
                t.add(s.substring(i, j + 1));
                dfs(s, j + 1, t);
                t.remove(t.size() - 1);
            }
        }
    }
}

// OJ: https://leetcode.com/problems/palindrome-partitioning/
// Time: O(N *  2^N)
// Space: O(N) extra space
class Solution {
    vector<vector<string>> ans;
    vector<string> tmp;
    bool isPalindrome(string &s, int i, int j) {
        while (i < j && s[i] == s[j]) ++i, --j;
        return i >= j;
    }
    void dfs(string &s, int start) {
        if (start == s.size()) {
            ans.push_back(tmp);
            return;
        }
        for (int i = start; i < s.size(); ++i) {
            if (!isPalindrome(s, start, i)) continue;
            tmp.push_back(s.substr(start, i - start + 1));
            dfs(s, i + 1);
            tmp.pop_back();
        }
    }
public:
    vector<vector<string>> partition(string s) {
        dfs(s, 0);
        return ans;
    }
};

'''
>>> t = []
>>> t.append(1)
>>> t.append(2)
>>> t.append(3)
>>> t
[1, 2, 3]
>>> t.pop(-1)
3
>>> t
[1, 2]
>>> t.pop()
2
>>> t
[1]


>>> t = [1,2,3]
>>> t.pop(0)
1
>>> t
[2, 3]


>>> t = [1,2,3]
>>> t.pop(1)
2
>>> t
[1, 3]
'''
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        ans = []
        n = len(s)
        dp = [[False] * n for _ in range(n)]

        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                # <=3 also working, same as <=1
                # i==j, or i+1==j
                dp[i][j] = s[i] == s[j] and (abs(i - j) <= 1 or dp[i + 1][j - 1])

        def dfs(s, i, t):
            nonlocal n # note: still pass OJ without this nonlocal. default is non-local
            if i == n:
                ans.append(t.copy())
                return
            for j in range(i, n): # including single char dp[i][i]
                if dp[i][j]:
                    t.append(s[i : j + 1])
                    dfs(s, j + 1, t)
                    t.pop(-1)

        dfs(s, 0, [])
        return ans

###########

class Solution(object): # iteration, real dp
  def partition(self, s):
    """
    :type s: str
    :rtype: List[List[str]]
    """
    pal = [[False for i in range(0, len(s))] for j in range(0, len(s))]
    ans = [[[]]] + [[] for _ in range(len(s))] # length is n+1

    for i in range(0, len(s)):
      for j in range(0, i + 1):
        if (s[j] == s[i]) and ((j + 1 > i - 1) or (pal[j + 1][i - 1])):
          pal[j][i] = True
          for res in ans[j]:
            a = res + [s[j:i + 1]]
            ans[i + 1].append(a)
    return ans[-1]

func partition(s string) [][]string {
	n := len(s)
	dp := make([][]bool, n)
	var ans [][]string
	for i := 0; i < n; i++ {
		dp[i] = make([]bool, n)
		for j := 0; j < n; j++ {
			dp[i][j] = true
		}
	}
	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			dp[i][j] = s[i] == s[j] && dp[i+1][j-1]
		}
	}

	var dfs func(s string, i int, t []string)
	dfs = func(s string, i int, t []string) {
		if i == n {
			ans = append(ans, append([]string(nil), t...))
			return
		}
		for j := i; j < n; j++ {
			if dp[i][j] {
				t = append(t, s[i:j+1])
				dfs(s, j+1, t)
				t = t[:len(t)-1]
			}
		}
	}

	var t []string
	dfs(s, 0, t)
	return ans
}

using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<IList<string>> Partition(string s) {
        if (s.Length == 0) return new List<IList<string>>();

        var paths = new List<int>[s.Length];
        for (var i = 0; i < s.Length; ++i)
        {
            int j, k;
            for (j = i, k = i + 1; j >= 0 && k < s.Length; --j, ++k)
            {
                if (s[j] == s[k])
                {
                    if (paths[k] == null)
                    {
                        paths[k] = new List<int>();
                    }
                    paths[k].Add(j - 1);
                }
                else
                {
                    break;
                }
            }
            for (j = i, k = i; j >= 0 && k < s.Length; --j, ++k)
            {
                if (s[j] == s[k])
                {
                    if (paths[k] == null)
                    {
                        paths[k] = new List<int>();
                    }
                    paths[k].Add(j - 1);
                }
                else
                {
                    break;
                }
            }
        }

        var prevs = new List<int>[s.Length];
        for (var i = 0; i < s.Length; ++i)
        {
            if (paths[i] != null)
            {
                foreach (var path in paths[i])
                {
                    if (path < 0 || prevs[path] != null)
                    {
                        if (prevs[i] == null)
                        {
                            prevs[i] = new List<int>();
                        }
                        prevs[i].Add(path);
                    }
                }
            }
        }

        var results = new List<IList<string>>();
        var temp = new List<string>();
        GenerateResults(prevs, s, s.Length - 1, temp, results);
        return results;
    }

    private void GenerateResults(List<int>[] prevs, string s, int i, IList<string> temp, IList<IList<string>> results)
    {
        if (i < 0)
        {
            results.Add(temp.Reverse().ToList());
        }
        else
        {
            foreach (var prev in prevs[i])
            {
                temp.Add(s.Substring(prev + 1, i - prev));
                GenerateResults(prevs, s, prev, temp, results);
                temp.RemoveAt(temp.Count - 1);
            }
        }
    }
}

function partition(s: string): string[][] {
    const n = s.length;
    const f: boolean[][] = new Array(n)
        .fill(0)
        .map(() => new Array(n).fill(true));
    for (let i = n - 1; i >= 0; --i) {
        for (let j = i + 1; j < n; ++j) {
            f[i][j] = s[i] === s[j] && f[i + 1][j - 1];
        }
    }
    const ans: string[][] = [];
    const t: string[] = [];
    const dfs = (i: number) => {
        if (i === n) {
            ans.push(t.slice());
            return;
        }
        for (let j = i; j < n; ++j) {
            if (f[i][j]) {
                t.push(s.slice(i, j + 1));
                dfs(j + 1);
                t.pop();
            }
        }
    };
    dfs(0);
    return ans;
}

131 - Palindrome Partitioning

Question

Algorithm

Dynamic Programming (DP) Phase

Depth-First Search (DFS) Phase

Final Output

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Dynamic Programming (DP) Phase

Depth-First Search (DFS) Phase

Final Output

Code

All Problems

All Solutions