# Shouldn't we use DP in addition to DFS?

• I understand this problem can be solved easily with DFS. The basic idea is that for each palindromic prefix, recursively obtain the palindrome partitioning of the remaining substring. As far as I am concerned, this is, to say the least, an O(2^N) algorithm in the worst case (e.g., for strings like "aaaaa") since there are 2^N partitions.

However, in most implementations I saw online, people use an O(N) function to compute if each prefix is a palindrome, as in the following code, which can be found Here

``````public ArrayList<ArrayList<String>> partition(String s) {
ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();

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

ArrayList<String> partition = new ArrayList<String>();

return result;
}

private void addPalindrome(String s, int start, ArrayList<String> partition,
ArrayList<ArrayList<String>> result) {
//stop condition
if (start == s.length()) {
ArrayList<String> temp = new ArrayList<String>(partition);
return;
}

for (int i = start + 1; i <= s.length(); i++) {
String str = s.substring(start, i);
if (isPalindrome(str)) {
partition.remove(partition.size() - 1);
}
}
}

private boolean isPalindrome(String str) {
int left = 0;
int right = str.length() - 1;

while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}

left++;
right--;
}

return true;
}
``````

Since this function "isPalindrome" needs to be called once for every prefix, that would make the overall time complexity O(N * 2^N).

So my questions is: why don't we first use DP to find out if each substring is palindromic, which takes O(N^2) time and space? This would be nothing compared to the O(2^N) possible partitions, but saves us the need to call the O(N) isPalindrome function, thus brings down the overall time complexity to O(2^N) from O(N * 2^N).

I would really appreciate it if someone could point out if my reasoning is correct or not. Thank you!

• Sure, That's what I did. I think it's about the same amount of work as the non-DP version, and definitely a better way.

• I believe your algorithm will work because in case like {"a", "a", "aaa"} and {"aa", "aaa"}, you can avoid judging the substr[2,4],which is "aaa",multiple times.

• Here is my DP + DFS solution, which takes 44ms. But still in the worst situation, TC = O(2^n)

``````class Solution {
private:
void Find(string s, bool *dp, int n, int start, vector<string> &vstr, vector<vector<string>> &ret)
{
for(int i = start; i < n; i ++)
{
if(dp[start*n+i])
{
vstr.push_back(s.substr(start, i-start+1));
if(i == n-1)
{
ret.push_back(vstr);
}
else
{
Find(s, dp, n, i+1, vstr, ret);
}
vstr.pop_back();
}
}
}
public:
vector<vector<string>> partition(string s) {
int n = s.size();
vector<vector<string>> ret;
if(n == 0)return ret;
bool *dp = new bool[n*n];
for(int i = 0; i < n*n; i ++)
dp[i] = false;
dp[0] = true;
for(int i = 1; i < n; i ++)
{
dp[i*n+i] = true;
if(s[i] == s[i-1])
dp[(i-1)*n+i] = true;
}
for(int i = 2; i < n; i ++)
{
for(int j = 0; j+i < n; j ++)
{
if(s[j] == s[j+i] && dp[(j+1)*n+j+i-1])
dp[j*n+j+i] = true;
}
}
vector<string> vstr;
Find(s, dp, n, 0, vstr, ret);
return ret;
}
};``````

• I used dp+dfs. I use DP to compute every palindrome and store it in a 2d-array. array[i][j] means it is a palindrome from i to j.
My code is a bit longer than others. and it takes 20 ms.

• Here comes my DP + DFS non-recursive version:

``````class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
const int n = s.size();
if (0 == n) return result;

vector<vector<bool>> isPal(n, vector<bool>(n, false));

for (int i = n - 1; i >= 0; i--)
{
for (int j = i; j < n; j++)
{
isPal[i][j] =
(s[i] == s[j]) &&
((j - i < 2 ) || isPal[i + 1][j - 1]);
}
}

vector<string> current;
vector<pair<int, int>> stack;
int x = 0;
int y = 0;
stack.push_back(make_pair(x, y));
current.push_back(s.substr(0, 1));
bool forward = true;

while (!stack.empty())
{
pair<int, int> item = stack.back();
if (item.second == n - 1)
{
result.push_back(current);
stack.pop_back();
current.pop_back();
forward = false;
}
else
{
x = item.first;
y = item.second;
if (forward)
{
stack.push_back(make_pair(y + 1, y + 1));
current.push_back(s.substr(y + 1, 1));
}
else
{
y++;
while (y < n && !isPal[x][y])
y++;

if (y == n)
{
stack.pop_back();
current.pop_back();
}
else
{
stack.pop_back();
current.pop_back();

stack.push_back(make_pair(x, y));
current.push_back(s.substr(x, y - x + 1));
forward = true;
}
}
}
}

return result;
}
};``````

• Use dp + dfs. More Readable code. map_pali is all palindrome pair. We can use it to decrease search space in dfs function.

``````class Solution {
private:
vector<vector<string> > res;
vector<string> rec;
vector<vector<int> > map_pali;
public:
vector<vector<string>> partition(string s) {
int n = s.length();
if (s.length() == 0) return res;
vector<vector<bool> > map = vector<vector<bool> >(n, vector<bool>(n, false));
map_pali.resize(n);
for (int i = n - 1; i >= 0; --i)
{
for (int j = i; j < n; ++j)
{
map[i][j] = s[i] == s[j] && (j - i < 2 || map[i + 1][j - 1]);
if (map[i][j]) map_pali[i].push_back(j);
}
}
dfs(s,0);
return res;
}
void dfs(string s, int end)
{
if (s.length() == end)
{
res.push_back(rec);
return;
}
for (int i = 0; i < map_pali[end].size(); ++i)
{
int endidx=map_pali[end][i]+1;
if (endidx<s.length() && map_pali[endidx].size() == 0) continue;
rec.push_back(s.substr(end,endidx-end));
dfs(s,endidx);
rec.pop_back();
}
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.