LeetCode Problem : Palindrome Partitioning II

Problem

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Code

void palTable(string s,int n,vector<vector<bool> >& p) {
    for(int i = 0;i < n;++i)
        p[i][0] = true;
    for(int i = 0;i < n - 1;++i){
        if(s[i] == s[i+1]){
            p[i][1] = true;
        }
    }
    for(int len = 3;len <= n;++len){
        for(int i = 0;i <= n - len;++i){
            if(p[i+1][len-3] && s[i] == s[i + len - 1]){
                p[i][len - 1] = true;
            }
        }
    }
}
int minCut(string s) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    int n = s.size();
    vector<vector<bool> > p(n,vector<bool>(n,false));
    palTable(s,n,p);
    deque<int> Q;
    vector<int> level_num(n);
    vector<bool> visited(n,false);
    Q.push_back(0);
    level_num[0] = 0;
    while(!Q.empty()){
        int i = Q.front();
        Q.pop_front();
        for(int j = i + 1;j <= n; ++j){
            if(!visited[j]){
                if(p[i][j - i - 1]){
                    if(j == n)
                        return level_num[i];
                    level_num[j] = level_num[i] + 1;
                    visited[j] = true;
                    Q.push_back(j);
                }
            }
        }
    }
    return 0;
}