LeetCode LCR 020. 回文子串

Categories:

题目描述
思路分析
1. 解法一：中心扩展法（推荐）
2. 解法二：动态规划
相似题目

题目描述

✅ LCR 020. 回文子串

思路分析

解法一：中心扩展法（推荐）

核心思路：

回文串具有对称性，枚举每个可能的中心，从中心向两侧扩展，每成功扩展一步即发现一个新的回文子串，计数加 1。

中心分两类：奇数长度回文的中心是单个字符 s[i]，从 (i, i) 出发；偶数长度回文的中心是相邻两字符的间隙，从 (i, i+1) 出发。

共 2n-1 个中心（n 个奇数中心 + n-1 个偶数中心），对每个中心执行一次扩展。

复杂度分析：

时间复杂度：O(n²)，其中 n 表示字符串长度，共 2n-1 个中心，每个中心最多扩展 O(n) 次

空间复杂度：O(1)，只使用常数个变量

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int res = 0;
        for (int i = 0; i < n; i++) {
            // 以 s[i] 为中心，枚举奇数长度回文
            res += expand(s, i, i);
            // 以 s[i] 和 s[i+1] 之间为中心，枚举偶数长度回文
            res += expand(s, i, i + 1);
        }
        return res;
    }

    private int expand(String s, int left, int right) {
        int count = 0;
        // 向两侧扩展，每满足条件就发现一个回文子串
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}

func countSubstrings(s string) int {
	n := len(s)
	res := 0

	// expand 从 (left, right) 向两侧扩展，返回以此为中心的回文子串数量
	expand := func(left, right int) {
		for left >= 0 && right < n && s[left] == s[right] {
			res++
			left--
			right++
		}
	}

	for i := 0; i < n; i++ {
		// 奇数长度：以 s[i] 为中心
		expand(i, i)
		// 偶数长度：以 s[i] 和 s[i+1] 之间为中心
		expand(i, i+1)
	}

	return res
}

解法二：动态规划

核心思路：

定义 dp[i][j] 表示 s[i..j] 是否是回文串，若是则计数加 1。

状态转移：dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i+1][j-1])。

枚举顺序：按子串长度从小到大枚举，确保计算 dp[i][j] 时 dp[i+1][j-1] 已就绪。

复杂度分析：

时间复杂度：O(n²)，其中 n 表示字符串长度，需填满 n×n 的 dp 表

空间复杂度：O(n²)，其中 n 表示字符串长度，需要 n×n 的布尔数组

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int res = 0;

        // 按子串长度从小到大枚举，确保状态转移时依赖的子问题已计算
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    // 长度为 1 或 2 时，首尾相等即是回文
                    if (j - i <= 2) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j]) {
                    res++;
                }
            }
        }
        return res;
    }
}

func countSubstrings(s string) int {
	n := len(s)
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
	}
	res := 0

	// 按子串长度从小到大枚举，确保状态转移时依赖的子问题已计算
	for length := 1; length <= n; length++ {
		for i := 0; i <= n-length; i++ {
			j := i + length - 1
			if s[i] == s[j] {
				// 长度为 1 或 2 时，首尾相等即是回文
				if j-i <= 2 {
					dp[i][j] = true
				} else {
					dp[i][j] = dp[i+1][j-1]
				}
			}
			if dp[i][j] {
				res++
			}
		}
	}
	return res
}

相似题目

题目	难度	考察点
5. 最长回文子串	中等	中心扩展、动态规划
516. 最长回文子序列	中等	动态规划
131. 分割回文串	中等	回溯、动态规划
132. 分割回文串 II	困难	动态规划
9. 回文数	简单	数学、回文检测
234. 回文链表	简单	链表、双指针
680. 验证回文串 II	简单	双指针、字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/18287440