LC.P1147[段式回文]

思路

采用贪心策略，从字符串的前后缀同时开始匹配，若相同，则分割，答案+2（因为题目要求尽可能多的分割），若遍历到字符串长度的一半时仍无法分割，则返回1。

方法一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int longestDecomposition(String text) {
        if (text.isEmpty()) return 0; // 若分割为空字符串，返回0
        int n = text.length();
        for (int i = 1; i <= n / 2; ++i) {
            // 若前后缀相等，则立刻分割
            if (text.substring(0, i).equals(text.substring(n - i))) {
                return longestDecomposition(text.substring(i, n - i)) + 2;
            }
        }
        return 1; // 无法分割
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n)$

方法二：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int longestDecomposition(String text) {
        int ans = 0;
        while (!text.isEmpty()) {
            int i = 1, n = text.length();
            while (i <= n / 2 && !text.substring(0, i).equals(text.substring(n - i))) ++i;
            if (i > n / 2) { // 无法分割
                ++ans;
                break;
            }
            ans += 2;
            text = text.substring(i, n - i);
        }
        return ans;
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n)$