Whats the O(n) space idea in Longest Palindromic Substring DP solution


  • 0
    L

    what's the O(n) space idea in Longest Palindromic Substring DP solution?


  • 0

  • 0
    L

    See below:
    // code

    string longestPalindrome(string s) {
    if (s.length() <= 1) { return s; }

    	//O(3*N) space
    	bool* dplastlast = new bool[s.length()];
    	bool* dplast = new bool[s.length()];
    	bool* dpcurr = new bool[s.length()];
    	for (int i = 0; i < s.length(); ++i) {
    		dplastlast[i] = true;
    		dplast[i] = true;
    		dpcurr[i] = true;
    	}
    
    	int maxlen = 1, maxstart = 0;
    	for (int len = 1; len<s.length(); ++len) {
    		for (int i = 0; i < s.length() - len; ++i) {
    			dpcurr[i] = false;
    			if (s[i] == s[i + len]) {
    				dpcurr[i] = (len <= 2) || (len>2 && dplastlast[i + 1]);
    			}
    			if (dpcurr[i] && (len + 1)>maxlen) {
    				maxlen = len + 1;
    				maxstart = i;
    			}
    		}
    		// update after one iteration
    		bool* tmp = dplastlast;
    		dplastlast = dplast;
    		dplast = dpcurr;
    		dpcurr = tmp;
    	}
    
    	return s.substr(maxstart, maxlen);
    }

Log in to reply
 

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