C++ 6ms: Keep Track of All, with Only O(n) Space


  • 0
    _

    Summary

    In the beginning, make sure you understand what a palindrome means. A palindrome is a string which reads the same in both directions. For example, ”aba” is a palindrome, while ”abc” is not.

    Now we can think of palindrome in another way: a palindrome is a sequence which mirrors around its center. What’s more, the this “center” can be:
    ① an exact char in the sequence, eg. “madamImadam” (Madam, I’m Adam), or
    ② between two chars, eg. “neveroddoreven” (Never odd or even).

    Section 1: To get all possible partitioning

    For the sake of concise expression, we use s[i, j] to represent string: s[i], s[i+1], …, s[j]

    Now Let’s Think of a string s with length n: s[0, n-1] (s[0], s[1], s[2], …, s[n-1])
    It’s easy to understand that:
    Assume that s[i, j] (0 <= i <= j <= n-1)is a palindrome, then all partitioning of s[i, n-1] with s[i, j] as the first substring would be:

    {{s[i, j], partitioning-j} | partitioning-j ∈ {all partitioning of s[j+1, n-1]}}
    

    Furthermore, we can just enumerate all possible j ∈[i, n-1] with a loop, to get all possible partitioning of s[i, n-1]
    In the case i=0, we get all possible partitioning.

    Section 2: Keep track of whether a substring is a palindrome

    The easiest way to check whether a substring s[i, j] is a palindrome is to check its chars “two” by “two”:

    bool isPalindrome(string& s, int i, int j) {
    	while(i < j) {
    		if(s[i++] != s[j--])
    			return false;
    	}
    	return true;
    }
    

    But if we do so, for the same substring s[i, j], we may check it for many times in the recursive process we’ve introduced in section 1.

    To solve this problem, the intuitive idea is that using extra space to keep track of whether a substring s[i, j] is palindrome. For example,
    0_1509719460921_1.png

    Now, for each substring s[i, j], we just need to call isPalindrome() for the first time, and then check the value of isPal[i][j] later.

    The Space Complexity of using isPal[ ][ ] is O(n²)

    Section 3: Keep track, but with space O(n)

    Recall that a palindrome is a sequence which mirrors around its center, here we call it the “intermediate point”.

    Now given a substring s[k-m, k+m] i.e. ( s[k-m], s[k-m+1], …, s[k-1], s[k], s[k+1], …, s[k+m-1], s[k+m] ) with s[k] be the “intermediate point”.

    0_1509720132486_Screen Shot 2017-11-03 at 10.40.36 PM.png
    Assume that s[k-m, k+m] is a palindrome, then how about s[k-1, k+1], s[k-2, k+2], …, s[k-m+1, k+m-1]?

    We can easily come to a conclusion that: all the substrings sharing the same “intermediate point” with a known palindrome and shorter than it, are palindromes too.

    As shown in the Summary, the “intermediate point” can also between 2 chars. As a result, a string with n chars would have n+(n-1) “intermediate points”.

    Based on this idea, we can build a data structure to save the longest length of palindrome with s[k]/(s[k], s[k+1]) as the “intermediate points”:

    int findLongest(string& s, int i, int j)  {        
    	int len = 0;        
    	while(i>=0 && j<s.size() && s[i--]==s[j++])            
    		len+=2;        
    	return len;    
    }
    
    vector<int> longestAt;
    for(int i=0; i < s.size()-1; i++) {
    	longestAt.push_back( findLongest(s, i, i)-1 );
    	longestAt.push_back( findLongest(s, i, i+1) );        
    }
    longestAt.push_back( findLongest(s, n, n)-1 );
    

    Here is the diagrammatic sketch of the “longestAt” vector:
    0_1509720631281_pic2.png
    The intermediate point s[k] corresponds to longestAt[2k], while the inner point between s[k] and s[k+1] corresponds to longestAt[2k+1].Then which one does the intermediate point of substirng s[i, j] corresponds to?

    Take s[2, 4] and s[2, 5] as examples:
    0_1509720859270_pic3.png
    For s[2, 4], the mid = (i+j)/2 = (2+4)/2 = 3, corresponding to longestAt[2xmid] = longestAt[2x3] = longestAt[(i+j)/2x2] = longestAt[i+j]
    For s[2, 5], the mid = (i+j)/2 = (2+5)/2 = 3(.5), corresponding to longestAt[2x3+1] = longestAt[2x(i+j)/2] = longestAt[i+j]

    Generally, the index of the intermediate point of s[i, j] is computed as:

    index(s[i, j]) = (i+j)/2*2+(i+j)%2 = 2*(i+j)/2 = i+j
    

    i.e. s[i, j] corresponds to longestAt[i+j].
    For the length of s[i, j] is (j-i+1), we can finally determine whether s[i, j] is a palindrome by checking whether longestAt[i+j] is not shorter than (j-i+1):
    0_1509721196929_2.png

    Code Example [Accepted, 6ms]

    class Solution {
    private:
        int findLongest(string& s, int i, int j) {
            int len = 0;
            while(i>=0 && j<s.size() && s[i--]==s[j++])
                len+=2;
            return len;
        }
        
        void search(vector< vector <string> >& res, vector<string>& part, vector<int>& longestAt, string& s, int i) {
            if(i == s.size())   res.push_back(part);
            for(int j=i; j < s.size(); j++) {
                if(longestAt[i+j] < j-i+1)    continue;
                part.push_back(s.substr(i, j-i+1));
                search(res, part, longestAt, s, j+1);
                part.pop_back();
            }
            return;
        }
        
    public:
        vector< vector<string> > partition(string s) {
            vector< vector<string> > res;
            vector<string> part;
            vector<int> longestAt;
            int n = s.size()-1;
            for(int i=0; i < n; i++) {
                longestAt.push_back( findLongest(s, i, i)-1 );
                longestAt.push_back( findLongest(s, i, i+1) );
            }
            longestAt.push_back( findLongest(s, n, n)-1 );
            search(res, part, longestAt, s, 0);
            return res;
        }
    };
    

    Complexity Analysis
    Time complexity : O(n^2) (construction of longestAt: O(n^2), while recursion+loop: O(n^2))
    Space complexity : O(n^2) for all possible partitioning, while only O(n) for the vector<int> longestAt.


Log in to reply
 

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