代码随想录-Day52

647. 回文子串

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

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

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

示例 1：

输入：s = “abc”

输出：3

解释：三个回文子串: “a”, “b”, “c”

示例 2：

输入：s = “aaa”

输出：6

解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

方法一：

class Solution {
    public int countSubstrings(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        boolean[][] dp = new boolean[len][len];
        int result = 0;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j  
这段代码是用于解决「最长回文子序列」问题的Java实现。给定一个字符串 s，目标是找到 s 中最长的回文子序列的长度。这里所说的“子序列”是指由原字符串中删除若干个字符（也可以不删除）后，保持剩余字符相对顺序不变所组成的新字符串。
 
代码解析
 
 
初始化动态规划数组:
 
  
创建一个二维数组 dp，其大小为 (len + 1) x (len + 1)，其中 len 是字符串 s 的长度。dp[i][j] 的值代表 s 中从下标 i 到下标 j 的子串中最长回文子序列的长度。额外的一行和一列是为了方便边界条件的处理。
 
动态规划迭代:
 
  
从 len - 1 到 0 反向遍历字符串 s 的每个字符，作为子串的起始点 i。
对于每个起始点 i，从 i + 1 开始到字符串的末尾遍历每个可能的结束点 j。
对于每一对起始点和结束点 i 和 j： 
    
如果 s 在 i 和 j 位置的字符相等，那么 dp[i][j] 的值等于去掉这两个字符后子串的最长回文子序列长度加2，即 dp[i + 1][j - 1] + 2。
如果 s 在 i 和 j 位置的字符不相等，那么 dp[i][j] 的值取 dp[i + 1][j]、dp[i][j] 和 dp[i][j - 1] 中的最大值，代表从 i 到 j 的子串的最长回文子序列长度。
 
返回结果:
 
  
最后返回 dp[0][len - 1]，即整个字符串 s 的最长回文子序列的长度。
时间复杂度和空间复杂度
 

• 时间复杂度: O(n^2)，其中 n 是字符串 s 的长度。这是因为需要遍历所有可能的子串组合。
• 空间复杂度: O(n^2)，需要一个大小为 n x n 的动态规划数组 dp 来存储中间结果。

  总结

  这段代码通过动态规划方法，有效地解决了最长回文子序列问题。通过构建二维数组 dp 来追踪子串中可能的最长回文子序列的长度，避免了对每个子串进行单独的回文性和长度检查，从而提高了效率。在处理字符串回文相关问题时，这种方法是一种常见的有效策略。如果需要进一步优化空间复杂度，可以考虑使用滚动数组技术，但由于回文子序列问题的特性，这种优化可能不如其他问题那样明显或直接。在实际应用中，选择适当的优化策略取决于具体需求和资源限制。