LeetCode1147-段式回文

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/longest-chunked-palindrome-decomposition/

中文链接：https://leetcode-cn.com/problems/longest-chunked-palindrome-decomposition/

题目详述

段式回文 其实与 一般回文 类似，只不过是最小的单位是 一段字符 而不是 单个字母。

举个例子，对于一般回文 “abcba” 是回文，而 “volvo” 不是，但如果我们把 “volvo” 分为 “vo”、”l”、”vo” 三段，则可以认为 “(vo)(l)(vo)” 是段式回文（分为 3 段）。

给你一个字符串 text，在确保它满足段式回文的前提下，请你返回 段 的 最大数量 k。

如果段的最大数量为 k，那么存在满足以下条件的 a_1, a_2, …, a_k：

每个 a_i 都是一个非空字符串；
将这些字符串首位相连的结果 a_1 + a_2 + … + a_k 和原始字符串 text 相同；
对于所有1 <= i <= k，都有 a_i = a_{k+1 - i}。

示例 1：

1
2
3
输入：text = "ghiabcdefhelloadamhelloabcdefghi"
输出：7
解释：我们可以把字符串拆分成 "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)"。

示例 2：

1
2
3
输入：text = "merchant"
输出：1
解释：我们可以把字符串拆分成 "(merchant)"。

示例 3：

1
2
3
输入：text = "antaprezatepzapreanta"
输出：11
解释：我们可以把字符串拆分成 "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)"。

示例 4：

1
2
3
输入：text = "aaa"
输出：3
解释：我们可以把字符串拆分成 "(a)(a)(a)"。

提示：

  • text 仅由小写英文字符组成。
  • 1 <= text.length <= 1000

题目详解

  • 要使回文串的段的数量最大，就需要每个回文串的长度尽可能地短。
  • 从两端往中间遍历，从小到大枚举长度，如果满足回文串的条件，更新结果和和指针位置并进行下一轮操作；如果不满足，说明到达了中间最后一个回文串（这个回文串也可能不存在），结果加一跳出循环即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class LeetCode_01147 {

    public int longestDecomposition(String text) {
        char[] cs = text.toCharArray();
        int res = 0;
        for (int i = 0, j = cs.length - 1; i <= j; ) {
            boolean flag = true;
            for (int k = 1; i + k - 1 < j - k + 1; ++k) {
                if (check(cs, i, j - k + 1, k)) {
                    res += 2;
                    i += k;
                    j -= k;
                    flag = false;
                    break;
                }
            }
            // 中间最后一个回文串
            if (flag) {
                ++res;
                break;
            }
        }
        return res;
    }

    private boolean check(char[] cs, int i, int j, int k) {
        while (k-- > 0) {
            if (cs[i++] != cs[j++]) {
                return false;
            }
        }
        return true;
    }
}

也可以运用递归来解答本题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class LeetCode_01147 {

    public int longestDecomposition(String text) {
        if (text.isEmpty()) {
            return 0;
        }
        for (int i = 0, n = text.length(); i < n / 2; ++i) {
            if (text.substring(0, i + 1).equals(text.substring(n - 1 - i))) {
                return 2 + longestDecomposition(text.substring(i + 1, n - 1 - i));
            }
        }
        return 1;
    }
}