Any DP solution that takes less than 56ms?


  • 2
    E

    The DFS solution has a time complexity of O(2^n) while DP solution only takes about O(n^3). My DFS solution takes about 56ms, but my DP solution below takes more than 100ms, which makes me very confused. Can someone please tell me how to improve my DP code or provide one that takes less time than the DFS solution?

    //DP solution.
    vector<vector<string> > partition(string s) {
        const int len = s.size();
        vector<vector<string> > subPalins[len+1] ;
        subPalins[0] = vector<vector<string> >();
        subPalins[0].push_back(vector<string>());
        bool isPalin[len][len];
        for (int i = len - 1; i >= 0; --i)
        {
            for (int j = i; j < len; ++j)
            {
                isPalin[i][j] = (s[i] == s[j]) && ((j - i < 2) || isPalin[i+1][j-1]);
            }
        }
    
        for (int i = 1; i <= len; ++i)
        {
            subPalins[i] = vector<vector<string> >();
            for (int j = 0; j < i; ++j)
            {
                string rightStr = s.substr(j, i-j);
                if (isPalin[j][i-1]) {
                    vector<vector<string> > prePartition = subPalins[j];
                    for (int t = 0; t < prePartition.size(); ++t)
                    {
                        prePartition[t].push_back(rightStr);
                        subPalins[i].push_back(prePartition[t]);
                    }
                }
            }
        }
        return subPalins[len];
    }

  • 1
    W

    There is huge variation on the reported run-time. I ran the same DP code twice and got 88 ms and 64 ms.


  • 0
    S

    I didn't fully understand you solution. But it looks like you save if substring of the given string is palindrome, but not save the partition result of substrings.
    E.g. partition(String s) is if sub of s is palindrome, add sub at the head of the result of the rest of s.
    My apology if I did not understand your code correctly.


  • 0
    P
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to post as answer with more detail content. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    E

    I do save the partition of substrings in subPalins. subPalins[i] is the partition of substring s[0...i)


  • 0
    D

    I didn't fully understand you solution too, esp. isPalin[i][j] = (s[i] == s[j]) && ((j - i < 2) || isPalin[i+1][j-1]);

    Why j-I<2 instead of j-I<1?

    Thanks


  • 0
    K

    isPalin[i+1][j-1] can be found only when i + 1 <= j - 1 which equals to j - i >= 2
    so if we can't find isPalin[i+1][j-1] the condition must be !(j - i >= 2) = j - i < 2


Log in to reply
 

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