Solution with O(N^2) additional space and O(N^2) preprocessing time for all possible palindrome validations


#1

The additional space being O(N^2) is trivial, preProcess(i, j) will hold if A(i, j) is palindrome or not. For calculating it, consider the follow:

A(i, i) for all 0 < i < A.size() = true
A(i, i+1) = true iff A[i] = A[i + 1]
For the remainder, say A(10, 15), we can use the following standard: we check A(11, 14) [i.e the substring of A[10…15] without the initial and the final char], and, if this substring is palindrome, we check whether A[10] = A[15]. This approach is O(N^2)

Full code below:

void recursion( vector<string> current,
            int strPos,
            string &A,
            vector<vector<string> > &answ,
            vector<vector<bool> > &preProcessPalindrome) {
if (strPos == A.size()) {
    answ.push_back(current);
    return;
}

for (int i = strPos; i < A.size(); i++) {
    if (preProcessPalindrome[strPos][i]) {
        current.push_back(A.substr(strPos, i - strPos + 1));
        recursion(current, i + 1, A, answ, preProcessPalindrome);
        current.pop_back();
    }
}
}

vector<vector<string> > Solution::partition(string A) {
// Do not write main() function.
// Do not read input, instead use the arguments to the function.
// Do not print the output, instead return values as specified
// Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details
vector<vector<bool> > preProcessPalindrome(A.size(), vector<bool>(A.size(), false));

for (int i = 0; i < A.size(); i++) {
    preProcessPalindrome[i][i] = true;
    if (i + 1 < A.size())
        preProcessPalindrome[i][i + 1] = (A[i] == A[i + 1]);
}
for (int len = 3; len <= A.size(); len++) {
    for (int i = 0; i + len <= A.size(); i++) {
        int j = i + len - 1;
        preProcessPalindrome[i][j] = preProcessPalindrome[i+1][j - 1] and (A[i] == A[j]);
        //printf("(%d, %d) = %d; ", i, j, (int) preProcessPalindrome[i][j]);
    }
}

//printf("finale(%d)", (int) preProcessPalindrome[0][A.size() - 1]);

vector<vector<string> > answ;
recursion(vector<string>(), 0, A, answ, preProcessPalindrome);
return answ;

}