131. Palindrome Partitioning

  • 31.6%

https://leetcode.com/problems/palindrome-partitioning/#/description

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

Return all possible palindrome partitioning of s.

1
2
3
4
5
6
7
For example, given s = "aab",
Return

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

https://discuss.leetcode.com/topic/10955/clean-c-backtracking-solution

Clean C++ backtracking solution

The Idea is simple: loop through the string, check if substr(0, i) is palindrome. If it is, recursively call dfs() on the rest of sub string: substr(i+1, length). keep the current palindrome partition so far in the ‘path’ argument of dfs(). When reaching the end of string, add current partition in the result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string> > ret;
if(s.empty()) return ret;

vector<string> path;
dfs(0, s, path, ret);

return ret;
}

void dfs(int index, string& s, vector<string>& path, vector<vector<string> >& ret) {
if(index == s.size()) {
ret.push_back(path);
return;
}
for(int i = index; i < s.size(); ++i) {
if(isPalindrome(s, index, i)) {
path.push_back(s.substr(index, i - index + 1));
dfs(i+1, s, path, ret);
path.pop_back();
}
}
}

bool isPalindrome(const string& s, int start, int end) {
while(start <= end) {
if(s[start++] != s[end--])
return false;
}
return true;
}
};

https://discuss.leetcode.com/topic/15432/12ms-14-lines-c

12ms 14-lines C++

The problem has a nice structure that backtracking naturally fits in. The structure is, given a starting position idx, we search from idx till the end of the string s.length() - 1. Once we reach a position i such that the sub-string from idx to i (s.substr(idx, i - idx + 1)) is a palindrome, we add it to a temporary tmp. Then we recursively call the same function to process the remaining sub-string. Once we reach the end of the string, we add tmp into the result res of all the possible partitioning.

Then, backtracking happens! Remember that at position i, we find s.substr(idx, i - idx + 1) to be a palindrome and we immediately add it to tmp. It is obvious that there may be some position j such that j > i and s.substr(idx, j - idx + 1) is also a palindrome. So we need to recover to the state before adding s.substr(idx, i - idx + 1) to tmp and continue to find the next palindrome position after i. And we simply need to pop s.substr(idx, i - idx + 1) out of tmp to make things work.

Putting these together, we can write down the following code, which should be self-explanatory.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> tmp;
getPartition(s, 0, tmp, res);
return res;
}
private:
void getPartition(string& s, int idx, vector<string>& tmp, vector<vector<string>>& res) {
if (idx == s.length()) {
res.push_back(tmp);
return;
}
for (int i = idx, n = s.length(); i < n; i++) {
int l = idx, r = i;
while (l < r && s[l] == s[r]) l++, r--;
if (l >= r) {
tmp.push_back(s.substr(idx, i - idx + 1));
getPartition(s, i + 1, tmp, res);
tmp.pop_back();
}
}
}
};

https://discuss.leetcode.com/topic/19370/1-liner-python-ruby

1-liner Python, Ruby

Python:

Broken into several physical lines for readability, but still one logical line and just one simple statement.

1
2
3
4
5
def partition(self, s):
return [[s[:i]] + rest
for i in xrange(1, len(s)+1)
if s[:i] == s[i-1::-1]
for rest in self.partition(s[i:])] or [[]]

https://discuss.leetcode.com/topic/33425/python-recursive-iterative-backtracking-solution

Python recursive/iterative backtracking solution

Inspired by caikehe’s solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def partition(self, s):
res = []
self.dfs(s, [], res)
return res

def dfs(self, s, path, res):
if not s:
res.append(path)
return
for i in range(1, len(s)+1):
if self.isPal(s[:i]):
self.dfs(s[i:], path+[s[:i]], res)

def isPal(self, s):
return s == s[::-1]

https://discuss.leetcode.com/topic/6186/java-backtracking-solution

Java: Backtracking solution.

if the input is “aab”, check if [0,0] “a” is palindrome. then check [0,1] “aa”, then [0,2] “aab”.
While checking [0,0], the rest of string is “ab”, use ab as input to make a recursive call.

image

in this example, in the loop of i=l+1, a recursive call will be made with input = “ab”.
Every time a recursive call is made, the position of l move right.

How to define a correct answer?

Think about DFS, if the current string to be checked (Palindrome) contains the last position, in this case “c”, this path is a correct answer, otherwise, it’s a false answer.

image

line 13: is the boundary to check if the current string contains the last element.
l>=s.length()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
List<List<String>> resultLst;
ArrayList<String> currLst;
public List<List<String>> partition(String s) {
resultLst = new ArrayList<List<String>>();
currLst = new ArrayList<String>();
backTrack(s,0);
return resultLst;
}
public void backTrack(String s, int l){
if(currLst.size()>0 //the initial str could be palindrome
&& l>=s.length()){
List<String> r = (ArrayList<String>) currLst.clone();
resultLst.add(r);
}
for(int i=l;i<s.length();i++){
if(isPalindrome(s,l,i)){
if(l==i)
currLst.add(Character.toString(s.charAt(i)));
else
currLst.add(s.substring(l,i+1));
backTrack(s,i+1);
currLst.remove(currLst.size()-1);
}
}
}
public boolean isPalindrome(String str, int l, int r){
if(l==r) return true;
while(l<r){
if(str.charAt(l)!=str.charAt(r)) return false;
l++;r--;
}
return true;
}
}

https://discuss.leetcode.com/topic/2884/my-java-dp-only-solution-without-recursion-o-n-2

My Java DP only solution without recursion. O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
public static List<List<String>> partition(String s) {
int len = s.length();
List<List<String>>[] result = new List[len + 1];
result[0] = new ArrayList<List<String>>();
result[0].add(new ArrayList<String>());

boolean[][] pair = new boolean[len][len];
for (int i = 0; i < s.length(); i++) {
result[i + 1] = new ArrayList<List<String>>();
for (int left = 0; left <= i; left++) {
if (s.charAt(left) == s.charAt(i) && (i-left <= 1 || pair[left + 1][i - 1])) {
pair[left][i] = true;
String str = s.substring(left, i + 1);
for (List<String> r : result[left]) {
List<String> ri = new ArrayList<String>(r);
ri.add(str);
result[i + 1].add(ri);
}
}
}
}
return result[len];
}
}

Here the pair is to mark a range for the substring is a Pal. if pair[i][j] is true, that means sub string from i to j is pal.

The result[i], is to store from beginng until current index i (Non inclusive), all possible partitions. From the past result we can determine current result.


https://discuss.leetcode.com/topic/37756/java-dp-dfs-solution

Java DP + DFS solution

The normal dfs backtracking will need to check each substring for palindrome, but a dp array can be used to record the possible break for palindrome before we start recursion.

Edit:

Sharing my thought process:

first, I ask myself that how to check if a string is palindrome or not, usually a two point solution scanning from front and back. Here if you want to get all the possible palindrome partition, first a nested for loop to get every possible partitions for a string, then a scanning for all the partitions. That’s a O(n^2) for partition and O(n^2) for the scanning of string, totaling at O(n^4) just for the partition. However, if we use a 2d array to keep track of any string we have scanned so far, with an addition pair, we can determine whether it’s palindrome or not by justing looking at that pair, which is this line if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])). This way, the 2d array dp contains the possible palindrome partition among all.

second, based on the prescanned palindrome partitions saved in dp array, a simple backtrack does the job.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i = 0; i < s.length(); 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(res, new ArrayList<>(), dp, s, 0);
return res;
}

private void helper(List<List<String>> res, List<String> path, boolean[][] dp, String s, int pos) {
if(pos == s.length()) {
res.add(new ArrayList<>(path));
return;
}

for(int i = pos; i < s.length(); i++) {
if(dp[pos][i]) {
path.add(s.substring(pos,i+1));
helper(res, path, dp, s, i+1);
path.remove(path.size()-1);
}
}
}
}

回溯法

https://discuss.leetcode.com/topic/46159/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partitioning/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> list = new ArrayList<>();
backtrack(list, new ArrayList<>(), s, 0);
return list;
}

public void backtrack(List<List<String>> list, List<String> tempList, String s, int start){
if(start == s.length())
list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < s.length(); i++){
if(isPalindrome(s, start, i)){
tempList.add(s.substring(start, i + 1));
backtrack(list, tempList, s, i + 1);
tempList.remove(tempList.size() - 1);
}
}
}
}

public boolean isPalindrome(String s, int low, int high){
while(low < high)
if(s.charAt(low++) != s.charAt(high--)) return false;
return true;
}
}
谢谢你,可爱的朋友。