LeetCode 1147. 段式回文

Categories:

题目描述
思路分析
1. 解法一：双指针分段匹配（推荐）
相似题目

题目描述

✅ 1147. 段式回文

思路分析

解法一：双指针分段匹配（推荐）

核心思路：

使用双指针从两端逐步扩展片段。

当左片段等于右片段时，计数加 2 并重置片段。

最后若中间仍有未匹配片段，计数加 1。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示字符串长度。

空间复杂度：O(n)，存储片段。

class Solution {
    public int longestDecomposition(String text) {
        int i = 0;
        int j = text.length() - 1;
        StringBuilder left = new StringBuilder();
        StringBuilder right = new StringBuilder();
        int ans = 0;

        while (i <= j) {
            left.append(text.charAt(i));
            right.insert(0, text.charAt(j));
            if (left.toString().equals(right.toString())) {
                ans += (i == j) ? 1 : 2;
                left.setLength(0);
                right.setLength(0);
            }
            i++;
            j--;
        }

        if (left.length() > 0) {
            ans++;
        }
        return ans;
    }
}

func longestDecomposition(text string) int {
    i, j := 0, len(text)-1
    left := make([]byte, 0)
    right := make([]byte, 0)
    ans := 0

    for i <= j {
        left = append(left, text[i])
        right = append([]byte{text[j]}, right...)
        if string(left) == string(right) {
            if i == j {
                ans++
            } else {
                ans += 2
            }
            left = left[:0]
            right = right[:0]
        }
        i++
        j--
    }

    if len(left) > 0 {
        ans++
    }
    return ans
}

相似题目

题目	难度	考察点
5. 最长回文子串	中等	回文
516. 最长回文子序列	中等	DP
647. 回文子串	中等	中心扩展
1147. 段式回文	困难	双指针
1312. 让字符串成为回文串的最少插入次数	困难	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2020/78391349