[LeetCode] Palindrome Partitioning II 解题笔记

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.

问题：对给定的字符串进行分割，使得每个子字符串都是回文的。求最小的分割情况。

假设将 s 分割为两段，[0, i-1], [i, n-1]，若 [0, i-1] 为回文字符串，则 ( [i, n-1] 的最小分割次数字符串数 + 1 ) 便是 s 以 i 为分割点最小分割情况的子字符串数。

将 i 从 1 到 n-1 遍历一边，便得到 s 依次以 i 为分割点得最小分割情况的子字符串数，其中最小的便是原问题的解。

利用 DP 思路，存储中间结构，避免重复的计算。 tailMinCutSC[i] 表示从下标i 到结尾的最小分割情况的子字符串数。

算法思路是正确的，但是扔到 LeetCode 却超时了。接下来进行多次优化：

1. 求解子问题时，将 substr 的操作改为了传引用 & 和下标来表示，优化效果不明显。仅从 1204 ms 加快到 936 ms 。

2. 求解 s[i, j] 是否是回文时，每次从 i 到 j 扫一遍，耗时太长。采用二维数组 PalinVV 记录全部可能的结果，减低时间复杂度。优化前的耗时我不太会分析，通过程序记录开看，是远远超过 O(n*n)的，进行这步优化后，使得整个算法时间复杂降为 O(n*n)。

3. 实现第2 步优化，本身也是一个 DP 思路。PalinVV[i][k](i <= k)，表示 s[i,k] 是否是回文，可以根据 PalinVV[i+1][k-1] 结果快速得到。对于 PalinVV 二维表格，从下往上计算，方便利用之前的结果。

vector<int> tailMinCutSC;

const int NEWONE = -1;

vector<vector<bool>> PalinVV;


/**
 * 判断字符串 s 的[sIdx, eIdx] 部分字符是否是回文字符串。
 *
 */
bool isPalindrome(const string& s, int sIdx, int eIdx){
    
    return PalinVV[sIdx][eIdx];
}


/**
 * 判断字符串 s 的[sIdx, eIdx] 部分字符是否是回文字符串。
 *
 */
bool isPalindrome(const string& s, int sIdx){
    
    return isPalindrome(s, sIdx, (int)s.size()-1);
}

/**
 * 对 s 字符串 [sIdx, n]部分进行回文分割，返回最小分割情况的子字符串数。
 *
 */
int palindromeCut(const string& s, int sIdx){
    
    if (isPalindrome(s, sIdx)) {
        
        tailMinCutSC[sIdx] = 1;
        return 1;
    }

    int minCutSC = (int)s.size() - sIdx;
    
    for (int i = sIdx + 1 ; i < s.size(); i++) {
        bool leftP = isPalindrome(s, sIdx, i-1);
        if (leftP == false) {
            continue;
        }
        int rightSC;
        if (tailMinCutSC[i] != NEWONE) {
            rightSC = tailMinCutSC[i];
        }else{
            rightSC = palindromeCut(s, i);
            tailMinCutSC[i] = rightSC;
        }
        
        int oneSolution = rightSC + 1;
        minCutSC = min(minCutSC, oneSolution);
        
    }
    
    return minCutSC;
}

/**
 * 求字符串 s 的任意子字符串是否是回文，结果存于二维布尔数组
 * 求解全部可能的子字符串，符合 overlapping & optimal subcontructure，可以采用 DP 思想加速求解。
 *
 */
void calculatePalinVV(string& s){
    
    vector<vector<bool>> vvtmp(s.size(), vector<bool>(s.size()));
    
    PalinVV = vvtmp;
    
    for (int i = (int)s.size()-1; i >= 0; i--) {
        PalinVV[i][i] = 1;
    }
    
    for (int i = (int)s.size()-2; i >= 0; i--) {
        if (s[i] == s[i+1]) {
            PalinVV[i][i+1] = 1;
        }else{
            PalinVV[i][i+1] = 0;
        }
    }
    
    
    for (int i = (int)s.size()-3; i >= 0; i--) {
        for (int k = (int)s.size()-1; k >= i + 2; k--) {
            if (s[i] == s[k] && PalinVV[i+1][k-1]) {
                PalinVV[i][k] = 1;
            }else{
                PalinVV[i][k] = 0;
            }
        }
    }
}


int minCut(string s) {
    
    calculatePalinVV(s);
    
    vector<int> tmp(s.size(), NEWONE);
    tailMinCutSC = tmp;
    
    
    int minSC = palindromeCut(s, 0);
    
    tailMinCutSC[0] = minSC;

    int minCutPoint = minSC - 1;
    
    return minCutPoint;
}

参考资料 :

[LeetCode] Palindrome Partitioning II, Solution, 水中的鱼