Shouldn't we use DP in addition to DFS?


  • 5
    S

    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>();
    addPalindrome(s, 0, partition, result);
    
    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);
    	result.add(temp);
    	return;
    }
    
    for (int i = start + 1; i <= s.length(); i++) {
    	String str = s.substring(start, i);
    	if (isPalindrome(str)) {
    		partition.add(str);
    		addPalindrome(s, i, partition, result);
    		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!


  • 0
    W

    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.


  • 0
    R

    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.


  • 8
    H

    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;
        }
    };

  • 3
    X

    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.


  • 4
    N

    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;
    	}
    };

  • 0
    H

    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();
        }
      }
    };

Log in to reply
 

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