- 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 | For example, given s = "aab", |

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 | class Solution { |

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 | class Solution { |

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 | def partition(self, s): |

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

Python recursive/iterative backtracking solution

Inspired by caikehe’s solution:

1 | def partition(self, s): |

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.

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.

line 13: is the boundary to check if the current string contains the last element.

l>=s.length()

1 | public class Solution { |

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 | public class Solution { |

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 | public class Solution { |

回溯法

1 | public class Solution { |