leetcode
leetcode 551 ~ 600
回文子串

回文子串

难度:

标签:

题目描述

代码结果

运行时间: 34 ms, 内存: 16.2 MB


/*
 * 思路:
 * 使用Java Stream进行回文子串的计算,
 * 通过IntStream生成索引并使用lambda表达式处理。
 */
import java.util.stream.IntStream;
 
public class SolutionStream {
    public long countSubstrings(String s) {
        return IntStream.range(0, s.length())
                .mapToLong(i -> IntStream.range(i, s.length())
                        .filter(j -> isPalindrome(s, i, j))
                        .count())
                .sum();
    }
 
    private boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

解释

方法:

这个题解的思路是先找出字符串中所有连续相同字符构成的子串,统计它们的回文子串数量。接着再枚举连续子串的两端,向两边拓展,统计由不同字符构成的回文子串数量。最后将两部分的数量相加得到答案。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在处理连续相同字符的子串时,可以直接使用公式 (1 + (j-i+1)) * (j-i+1) / 2 来计算回文子串的数量?
在连续相同字符的子串中,任何长度的子串都自然形成回文子串。例如一个长度为 n 的连续相同字符子串,可以形成 1 个长度为 n 的回文子串、2 个长度为 n-1 的回文子串,以此类推,直到 n 个长度为 1 的回文子串。这个数量可以用等差数列的求和公式计算,即 (1 + n) * n / 2。在这里,n 是连续相同字符的个数,即 (j-i+1)。
🦆
在向两边扩展检查回文子串时,为什么只需要检查一次每对字符即可断定是否为回文?是否有可能遗漏某些情况?
在向两边扩展检查回文子串时,每次扩展都是对称的,即从中心点或中心对称的字符对向两端同时扩展。如果在某个点对称的字符不相等,则该点不可能是回文的一部分,因此不需要进一步检查。由于回文的特性是对称的,一旦找到不对称的字符,可以立即断定不是回文,从而不会遗漏。
🦆
在枚举连续相同字符子串的两端并向两边扩展时,如果两边扩展遇到相同的字符会如何处理?
当在枚举连续相同字符子串的两端并向两边扩展时,如果扩展点的两边的字符相同,则这两个字符可以形成新的回文子串。此时,可以继续扩展,即再向外各移动一位,继续检查下一对字符是否相同,如果仍然相同,则继续形成更大的回文子串,这个过程会持续到找到不相同的字符为止。
🦆
为什么连续相同字符的子串处理完后,还需要单独处理向两边扩展的情况?
连续相同字符的子串处理完后能得到所有完全由相同字符组成的回文子串,但是复合回文子串,即由不同字符组成的回文子串还未被计算。因此,需要单独处理向两边扩展的情况,以便捕捉那些起始于一个固定的连续相同字符子串,但包含其他不同字符的更长回文子串。

相关问题

最长回文子串

给你一个字符串 s,找到 s 中最长的回文子串

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

 

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"
输出:"bb"

 

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

最长回文子序列

给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

 

示例 1:

输入:s = "bbbab"
输出:4
解释:一个可能的最长回文子序列为 "bbbb" 。

示例 2:

输入:s = "cbbd"
输出:2
解释:一个可能的最长回文子序列为 "bb" 。

 

提示:

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

回文子串

给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

 

示例 1:

输入:s = "abc"
输出:3
解释:三个回文子串: "a", "b", "c"

示例 2:

输入:s = "aaa"
输出:6
解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

 

提示:

  • 1 <= s.length <= 1000
  • s 由小写英文字母组成