第 226 场周赛 5666. 回文串分割 IV

Desciption

给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的

输入：s = "bcbddxy"
输出：false

Solution

知道马拉车算法（Manacher算法），就很简单啦

  1. 先用马拉车算法：扩展原串 s，得到 s'，计算 len 数组，len[i] 表示以第 i 个字符为中心的最长回文串的 向左向右延伸的长度。
  2. 枚举下标 i，枚举长度 j，检查三个子字符串，即 (0, i-1), (i, i+j), (i+j+1, s.length) 这三个字符串是不是回文串。体现在 s' 的下标就是 (1, (i + 1) * 2 -1), ((i + 1) * 2, (i + j) * 2), ((i + j) * 2 + 1, s'.length - 1)，判断这每个区间的中心位置 mid，看 len[mid] >= (区间长度 / 2 + 1)，如果是的话，表示该区间是回文串，否则则不是回文串

Code

    public boolean check(int L, int R, int[] len) {
        int mid = (L + R) >> 1;
        return len[mid] >= ((R - L) / 2 + 1);
    }
    public boolean checkPartitioning(String s) {
        StringBuilder builder = new StringBuilder();
        builder.append("@#");
        for(int i = 0; i < s.length(); ++i) {
            builder.append(s.charAt(i) + "#");
        }
        builder.append("!");
        String str = builder.toString();
        int id = 0, mx = 0, n = str.length();
        int[] len = new int[n];
        for(int i = 1; i < n - 1; ++i) {
            if (i < mx) {
                len[i] = Math.min(len[2 * id - i], mx - i);
            }
            while (str.charAt(i + len[i]) == str.charAt(i - len[i])) {
                ++len[i];
            }
            if (i + len[i] > mx) {
                mx = i + len[i];
                id = i;
            }

        }

        int m = s.length();
        boolean flag = false;
        for (int i = 1; i < m; ++i) {
            for (int j = 0; i + j < m; ++j) {
                int L = (i + 1) * 2, R = (i + j) * 2;
                if (check(1, L - 1, len) && check(L, R, len) && check(R + 1, n - 1, len)) {
                    flag = true;
                    break;
                }
            }
        }
        return flag;
    }