[1147].段式回文

[1147].段式回文

• • 題目
  • 函式原型
  • 貪心 + 哈希優化
  • 動態規劃

題目

[1147].段式回文：https://leetcode-cn.com/problems/longest-chunked-palindrome-decomposition/

比如 volvo 如果按照 3 段切分就是一個回文 (vo) (l) (vo)，分成 5 段就不是回文，請問最大可以分成幾段？

函式原型

int longestDecomposition(string text){}

貪心 + 哈希優化

一個回文單詞拆解的結構：

那我們從倆端開始，左邊第一個字母 == 右邊第一個字母？

倆種情況：

• 如果相同，就是一段回文，那繼續按照這個思路看左邊第二個字母 == 右邊第二個字母，

• 通常，不會相等，如 volvo 左、右邊第一個字母就不同 ，但只需要在延展一個字母就相同了，

  左邊下標往左推一個、右邊下標往右推一個，再看字母組合是否匹配，

class Solution {
public:
    int longestDecomposition(string text) {
        return Recursion( text, 0, text.length()-1 );
    }

    int Recursion(string s, int left, int right) {
        if( left > right ) // 空串
            return 0;
        for( int i = left, j = right; i < j; i++, j--)
            if( equals(s, left, i, j, right) )         // s[left, i] == s[j, right]？
                return 2 + Recursion(s, i + 1, j - 1); // 找到 2 段
        return 1;                                      // 不能分段
    }

    bool equals(string s, int l1, int r1, int l2, int r2) {
        for(int i=l1, j=l2; i<=r1 && j<=r2; i++, j++)  // s[l1, r1] == s[l2, r2]?
            if(s[i] != s[j])             // s[i] == s[j]?
                return false;
        return true;
    }
};

更簡潔的寫法：

• 前 i 個字符只要和后i個字符完全一致即視為匹配成功，每次遞回中，只要有一次匹配成功即退出回圈，

class Solution {
public:
    int longestDecomposition(string text) {
        for(int i = 1; i <= text.length()/2; ++i)
            if(text.substr(0, i) == text.substr(text.length()-i, i))
                return 2 + longestDecomposition(text.substr(i, text.length() - i*2));
        return text.length()>0 ? 1:0;
    }
};

不過，字串匹配的程序需要 O ( n ) O(n) O(n)，我們可以用哈希，把字串匹配變成整數匹配，只需要 O ( 1 ) O(1) O(1)，

• 左邊： 當 前 字 母 ? 10 + 新 字 母 當前字母 * 10 + 新字母 當前字母?10+新字母，如 123 ? 10 + 4 = 1234 123 * 10 + 4 = 1234 123?10+4=1234
• 右邊： 新 字 母 ? 1 0 l e n ? 1 + 當 前 字 母 新字母 * 10^{len-1} + 當前字母 新字母?10len?1+當前字母，如 4 ? 1 0 3 + 123 = 4123 4*10^{3}+123=4123 4?103+123=4123

比如 volvo ，左邊是 v、vo ，右邊是 o、vo（不是 ov），

if( equals(s, left, i, j, right) )         // s[left, i] == s[j, right]？

所以，在倆個子串判等的時候，使用哈希優化，

class Solution {
    long MOD = (long)(1e9 + 7);                            // 素數，防止溢位
    long pow26[];
    
public:
    int longestDecomposition(string text) {
        return Recursion( text, 0, text.length()-1 );
    }

    int Recursion(string s, int left, int right) {
        if( left > right ) // 空串
            return 0;
        
        long left_hash = 0, right_hash = 0;                 // 記錄左右哈希值
        long *pow26 = new long[s.length()];                 // 提前計算26的冪
        pow26[0] = 1;
        for(int i=1; i<s.length(); i++)
            pow26[i] = pow26[i - 1] *26 % MOD;              // 防止溢位

        for( int i = left, j = right; i < j; i++, j--){
            left_hash = (left_hash * 26 + (s[i] - 'a')) % MOD; // 采用 26 進制，a 對應 0
            right_hash = ((s[j] - 'a') * pow26[right - j] + right_hash) % MOD;

             if( left_hash == right_hash && equals(s, left, i, j, right) )        // s[left, i] == s[j, right]？
                return 2 + Recursion(s, i + 1, j - 1); // 找到 2 段
        }
        return 1;                                      // 不能分段
    }

    bool equals(string s, int l1, int r1, int l2, int r2) {
        for(int i=l1, j=l2; i<=r1 && j<=r2; i++, j++)  // s[l1, r1] == s[l2, r2]?
            if(s[i] != s[j])                           // s[i] == s[j]?
                return false;
        return true;
    }
};

動態規劃

思路：如果給定字串可以分解為 APA 形式，P為中間任意長度字串，則 APA 的段最大數量是 P 的段數量 + 2，

class Solution {
public:
    int longestDecomposition(string text) {
        int m = text.length();
        vector<int> dp((m+1)/2,1);
        if(m&1){
            dp.back() = 1;
        }
        int p = m/2-1;
        int q = (m+1)/2;
        for(int i =p;i>=0;i--){
            for(int j = i;j<=p;j++){
                if(text.substr(i,j-i+1)==text.substr(q+p-j,j-i+1)){
                    dp[i] = max(dp[i], j+1>=dp.size() ? 2:dp[j+1]+2);
                }
            }
        }
        if(dp[0]<0){
            return 1;
        }
        return dp[0];
    }
};