leetcode 1147

问题

Return the largest possible k such that there exists a_1, a_2, ..., a_k such that:

  • Each a_i is a non-empty string;
  • Their concatenation a_1 + a_2 + ... + a_k is equal to text;
  • For all 1 <= i <= k, a_i = a_{k+1 - i}.

Example 1:

1
2
3
Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:

1
2
3
Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:

1
2
3
Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".

Example 4:

1
2
3
Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".

Constraints:

  • text consists only of lowercase English characters.
  • 1 <= text.length <= 1000

分析

思路1: 使用动态规划

思路2: 贪心算法，每次总是尽量取最小的能够匹配的最长公共前后缀。证明：https://leetcode.com/problems/longest-chunked-palindrome-decomposition/discuss/350560/JavaC%2B%2BPython-Easy-Greedy-with-Prove

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 88ms
class Solution {
public:
    int longestDecomposition(string text) {
        int n = text.size();
        vector<int> dp(n, -1);
        dp[n/2] = n%2? 1: 0;
        return dfs(text, dp, 0);
    }
    int dfs(const string &text, vector<int> &dp, int i) {
        if (dp[i] >= 0)
            return dp[i];
        int ret = 1;
        for (int k = 1; i+k <= text.size()/2; ++k) {
            if (text.substr(i, k) == text.substr(text.size()-i-k, k)) {
                ret = max(ret, 2+dfs(text, dp, i+k));
            }
        }
        return dp[i] = ret;
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 4ms
class Solution {
public:
    int longestDecomposition(string text) {
        string l, r;
        int n = text.size();
        int ans = 0;
        for (int i = 0; i < n/2; ++i) {
            l += text[i];
            r = text[n-i-1] + r;
            if (l == r) {
                ans += 2;
                l = r = "";
            }
        }
        // 长度为偶数，并且未匹配部分是空，直接返回ans
        if ((n%2 == 0) && l == "" && r == "")
            return ans;
        // 长度为偶数，并且未匹配部分不是空
        // 或者长度为基数，中间部分独立为1
        return ans+1;
    }
};