Palindrome Partitioning II

题目：

Given a string s, cut s into some substrings such that every substring is a palindrome.

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

Example: Given s = "aab", Return 1 since the palindrome partitioning ["aa", "b"] could be produced using 1 cut.

分析：

其中解法1牺牲了空间，换来了时间；解法2因为判断palindrome是个线性的过程，把n^2编程了n^3，但是空间生了下来。在oj上面解法2过不了大数据的test case。

这题目如果用二维数组表示isPalindrome，index好难匹配上。

//state: f[i] means the minimum num of parlindrome in first i chars
//function: f[i] = min(f[i], f[j] + 1), given that j + 1 ~ i is palindrome
//init: f[i] = i; maximum palindrome in first i chars
//answer: f[n] - 1, number of palindrome - 1 = number of cuts

解法1：

class Solution {
public:
    /**
     * @param s a string
     * @return an integer
     */
    vector<vector<bool> > calculatePalindrome(string s) {
        int n = s.size();
        vector<vector<bool> > res(n, vector<bool>(n, false) );
        for (int i = 0; i < n; i++) {
            res[i][i] = true;
        }

        for (int i = 0; i < n; i++) {
            res[i][i + 1] = (s[i] == s[i + 1]);
        }

        for (int i = 2; i < n; i++) {
            for (int start = 0; start + i < n; start++) {
                res[start][start + i] = res[start + 1][start + i - 1] == true && s[start] == s[start + i];
            }
        }
        return res;

    }

    int minCut(string s) {
        // write your code here

        if (s.size() <= 1) {
            return 0;
        }

        int n = s.size();
        vector<int> f(n + 1, INT_MAX);

        for (int i = 0; i <= n; i++) {
            f[i] = i;
        }

        vector<vector<bool> > isPalindrome = calculatePalindrome(s);

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (isPalindrome[j][i - 1]) {
                    f[i] = min(f[i], f[j] + 1);
                }
            }
        }
        return f[n] - 1;
    }
};

解法2：

class Solution {
public:
    /**
     * @param s a string
     * @return an integer
     */
    bool isPalindrome(string substr) {
        for (int i = 0, j = substr.size() - 1; i < j; i++, j--) {
            if (substr[i] != substr[j]) {
                return false;
            }
        }
        return true;
    }

    int minCut(string s) {
        // write your code here
        if (s.size() <= 1) {
            return 0;
        }

        int n = s.size();
        vector<int> f(n + 1, INT_MAX);

        for (int i = 0; i <= n; i++) {
            f[i] = i - 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                string substr = s.substr(j, i - j);
                if (isPalindrome(substr)) {
                    f[i] = min(f[i], f[j] + 1);
                }
            }
        }
        return f[n];
    }
};