Question

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

131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

@tag-dp

Algorithm

The title requires finding all possible cases that can be divided into palindrome numbers, so all cases must be traversed.

For each substring, it is necessary to judge whether it is palindrome number or not, then there must be a judgment palindrome number The sub-function, also needs a DFS function for recursion, plus the original function, a total of three functions are needed to solve.

Or, apply DP. First create the dp array of the substring palindrome of the string s, where dp[i][j] indicates whether the substring in the range of [i, j] is a palindrome, so that no additional sub-functions are needed to determine whether the substring is a palindrome.

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):
                dp[i][j] = s[i] == s[j] and (abs(i - j) <= 1 or dp[i + 1][j - 1]) # <= 3 also working

        def dfs(s, i, t):
            nonlocal n
            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);
            }
        }
    }
}

131 - Palindrome Partitioning

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions