# 132 - Palindrome Partitioning II

解法一 - 暴力法

暴力法就是要試試看每一種可能的 substring 組合，看哪一種組合可以滿足每一個 substring 都是 palindrome，而且分割數最少。

class Solution {
public:
    int minCut(string s) {
        return findMinCut(s, 0, s.length()-1);    
    }

private:
    int findMinCut(string& s, int start, int end) {
        // if s is empty or s is palindrome, minCut == 0
        if(start >= end || isPalindrome(s, start, end))
            return 0;

        // the maximal number of cut == the number of all length-1 pieces
        int minCut = end-start; 

        // finetune 到這樣會過，但我不太懂為何不是
        // for(int I=start+1; i<end; i++)
        for(int i=start; i<=end; i++) {
            if(isPalindrome(s, start, i)) {
                minCut = min(minCut, 1+findMinCut(s, i+1, end));
            }
        }

        return minCut;
    }

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

        return true;
    }
};

暴力解仍然不意外地會 TLE，讓我們繼續優化下去。

解法二 - 暴力法 + memoization

對於 findMinCut() 跟 isPalindrome() 這兩個 function，我們都可以做 memoization，雖然這兩者會改變的都只有 start，不過方便起見，就都先用 2D 的 array 來記錄。

class Solution {
public:
    int minCut(string s) {
        vector<vector<int>> memo(s.length(), vector<int>(s.length(), -1));
        vector<vector<int>> memoIsPalindrome(s.length(), vector<int>(s.length(), -1));
        return findMinCut(memo, memoIsPalindrome, s, 0, s.length()-1);    
    }

private:
    int findMinCut(vector<vector<int>>& memo, vector<vector<int>>& memoIsPalindrome, string& s, int start, int end) {
        // if s is empty or s is palindrome, minCut == 0
        if(start >= end || isPalindrome(memoIsPalindrome, s, start, end))
            return 0;

        // the maximal number of cut == the number of all length-1 pieces
        if(memo[start][end] == -1) {
            int minCut = end-start; 
            for(int i=start; i<=end; i++) {
                if(isPalindrome(memoIsPalindrome, s, start, i)) {
                    minCut = min(minCut, 1+findMinCut(memo, memoIsPalindrome, s, i+1, end));
                }
            }

            memo[start][end] = minCut;
        }

        return memo[start][end];
    }

    bool isPalindrome(vector<vector<int>>& memoIsPalindrome, string& s, int i, int j) {
        int x=i, y=j;
        if(memoIsPalindrome[i][j] == -1) {
            memoIsPalindrome[i][j] = 1;
            while(x < y) {
                if(s[x++] != s[y--]) {
                    memoIsPalindrome[i][j] = 0;
                    break;
                }
            }
        }

        return memoIsPalindrome[i][j] == 1;
    }
};

總算是過了！雖然效率有點差：

Runtime: 316 ms, faster than 19.07% of C++ online submissions for Palindrome Partitioning II. Memory Usage: 35.3 MB, less than 40.00% of C++ online submissions for Palindrome Partitioning II.

解法三 - DP

經過解法二的淬煉，我們現在知道，需要兩個 dp table，一個紀錄 isPalindrome，一個紀錄 minCuts，實作出來如下：

class Solution {
public:
    int minCut(string s) {
        // isPalindrome[i][j] == true if s[i] - s[j] is a palindrome
        vector<vector<bool>> isPalindrome(s.length(), vector<bool>(s.length(), false));   

        // every string with one character is a palindrome
        for (int i = 0; i < s.length(); i++) {
            isPalindrome[i][i] = true;
        }

        // build isPalindrome table
        for (int start = s.length() - 1; start >= 0; start--) {
            for (int end = start + 1; end < s.length(); end++) {
                if (s[start] == s[end]) {
                    // if it's a two character string or if the remaining string is a palindrome too
                    if (end-start == 1 || isPalindrome[start+1][end-1]) {
                        isPalindrome[start][end] = true;
                    }
                }
            }
        }

        // now lets populate the second table, every index in 'cuts' stores the minimum cuts needed
        // for the substring from that index till the end
        vector<int> cuts(s.length(), 0);
        for (int start = s.length() - 1; start >= 0; start--) {
            int minCuts = s.length()-start; // maximum cuts

            for (int end = s.length() - 1; end >= start; end--) {
                if (isPalindrome[start][end]) {
                    // we can cut here as we got a palindrome
                    // also we dont need any cut if the whole substring is a palindrome
                    minCuts = (end == s.length() - 1) ? 0 : min(minCuts, 1 + cuts[end+1]);
                }
            }

            cuts[start] = minCuts;
        }

        return cuts[0];
    }
};