段式回文

Category Difficulty Likes Dislikes
algorithms Hard (56.88%) 46 -
Tags

hash-table

Companies

Unknown

你会得到一个字符串 text 。你应该把它分成 k 个子字符串 (subtext1, subtext2，…， subtextk) ，要求满足:

  • subtexti 是 非空 字符串
  • 所有子字符串的连接等于 text ( 即subtext1 + subtext2 + ... + subtextk == text )
  • subtexti == subtextk - i + 1 表示所有 i 的有效值( 即 1 <= i <= k )

返回k可能最大值。

示例 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)"。

提示：

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

双指针(c++)

通过双指针 left = 0, right = text.size()-1 动态维护两个字符串
因题目要求返回最大的k
得到 if (s1 == s2) { res += 2 }
子字符串分偶数次数和奇数次数，在维护s1, s2的过程中如果最后一次(s1 == s2)且left + 1 != right
则表示是奇数次数的子字符串

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
35
36
37
38
39
40
41
class Solution {
public:
    int longestDecomposition(string text) {
        int left = 0, right = text.size() - 1;
        int res = 0;

        /* 更新最新左右子字符串 */
        int leftLast = 0, rightLast = right;

        if (right == -1) {
            return res;
        }

        while (left < right) {
            string tmp0 = text.substr(left, 1), tmp1 = text.substr(right, 1);
            while (left < right && tmp0 != tmp1) {
                ++left;
                --right;
                tmp0 += text[left];
                tmp1 = text[right] + tmp1;
            }

            if (left >= right) {
                // ++res;
                break;
            } 
            res += 2;
            leftLast = left;
            rightLast = right;
            ++left;
            --right;
        }

        /* if (leftLast + 1) < (rightLast) && text.size() != 2就说明存在一个不相等子字符串 */
        if (leftLast + 1 != rightLast || (text.size() == 2 && text[0] != text[1])) {
            ++res;
        }

        return res;
    }
};