C++ solution of O(N^2)


#1

I think this is more comprehensive than suggested solution code.

bool isPalindrome(const string& A, int start, int end) {
while (start < end) {
if (A[start] != A[end]) {
break;
}
start++;
end–;
}

if (start >= end) return true;
else return false;

}

int Solution::minCut(string A) {
if (A.empty()) return 0;

vector<int> M(A.size(), 0);

M[0] = 1;
for (int i = 1; i<(int)A.size(); i++) {
    int min = M[i - 1] + 1;

    for (int j = i - 1; j >= 0; j--) {
        if (isPalindrome(A, j, i)) {
            int x;
            if (j>0) x = M[j - 1] + 1;
            else x = 1;

            if (x < min) min = x;
        }
    }
    M[i] = min;
}

return M[A.size() - 1] - 1;

}