代码随想录-Day52

发布于:2024-07-11 ⋅ 阅读:(19) ⋅ 点赞:(0)

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 < len; j++) {
                if (chars[i] == chars[j]) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        result++;
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { //情况三
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
}

这段代码是用于解决「回文子串」问题的Java实现,目标是计算字符串 s 中所有回文子串的数量。回文子串指的是正读和反读都一样的子串,例如 “aba” 或者 “aa”。代码通过动态规划的方法实现,利用一个二维布尔数组 dp 来追踪字符串中各子串是否为回文。

代码解析

  1. 初始化动态规划数组:

    • 创建一个二维布尔数组 dp,其大小为 (len x len),其中 len 是字符串 s 的长度。dp[i][j] 的值代表 s 中从下标 i 到下标 j 的子串是否为回文串。
  2. 动态规划迭代:

    • len - 10 遍历字符串 s 的每个字符,作为子串的起始点 i
    • 对于每个起始点 i,从 i 到字符串的末尾遍历每个可能的结束点 j
    • 对于每一对起始点和结束点 ij
      • 如果 sij 位置的字符相等,那么:
        • 如果 j - i <= 1,这意味着子串长度为1或2,这样的子串总是回文的,因此 dp[i][j] 被设置为 true 并且结果计数器 result 加1。
        • 如果 j - i > 1 并且 dp[i + 1][j - 1]true,这意味着去掉两端字符后剩余的子串是回文的,因此整个子串也是回文的,此时 dp[i][j] 被设置为 true 并且结果计数器 result 加1。
  3. 返回结果:

    • 最后返回 result,即字符串 s 中所有回文子串的数量。

时间复杂度和空间复杂度

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

总结

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

方法二:

class Solution {
    public int countSubstrings(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        
        int res = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
                    res++;
                    dp[i][j] = true;
                }
            }
        }
        return res;
    }
}

这段代码同样用于解决「回文子串」问题,目标是计算字符串 s 中所有回文子串的数量。通过使用动态规划方法,代码构建了一个二维布尔数组 dp 来追踪字符串中各子串是否构成回文。

代码解析

  1. 初始化动态规划数组:

    • 创建一个二维布尔数组 dp,其大小为 s.length() x s.length()dp[i][j] 的值为 true 当且仅当 s 中从下标 i 到下标 j 的子串构成回文。
  2. 动态规划迭代:

    • s.length() - 10 反向遍历字符串 s 的每个字符,作为子串的起始点 i
    • 对于每个起始点 i,从 i 开始到字符串的末尾遍历每个可能的结束点 j
    • 对于每一对起始点和结束点 ij
      • 如果 sij 位置的字符相等,并且满足以下任一条件:
        • 子串长度小于等于2 (j - i <= 1),这意味着任何单个字符或重复的两个字符总是构成回文。
        • 子串内部(即 dp[i + 1][j - 1])也是回文,这意味着去掉当前子串两端字符后剩余的部分构成回文。
      • 若上述条件满足,dp[i][j] 被设置为 true,表示从 ij 的子串构成回文,并且结果计数器 res 加1。
  3. 返回结果:

    • 最后返回 res,即字符串 s 中所有回文子串的数量。

时间复杂度和空间复杂度

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

总结

这段代码通过动态规划方法,有效地解决了回文子串计数问题。与之前提到的代码实现相比,这段代码在逻辑表达上更加简洁,但在核心算法思想和性能特征上是相同的。通过动态规划追踪子串是否为回文,避免了对每个子串进行单独的回文性检查,从而提高了整体效率。在实际应用中,这种动态规划方法是处理字符串回文问题的常用且高效的策略之一。如果对空间复杂度有更高要求,可以探索进一步的优化策略,如使用滚动数组技术,但通常这会以增加代码复杂度为代价。

方法三:

class Solution {
    public int countSubstrings(String s) {
        int len, ans = 0;
        if (s == null || (len = s.length()) < 1) return 0;
        //总共有2 * len - 1个中心点
        for (int i = 0; i < 2 * len - 1; i++) {
            //通过遍历每个回文中心,向两边扩散,并判断是否回文字串
            //有两种情况,left == right,right = left + 1,这两种回文中心是不一样的
            int left = i / 2, right = left + i % 2;
            while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
                //如果当前是一个回文串,则记录数量
                ans++;
                left--;
                right++;
            }
        }
        return ans;
    }
}

这段代码是用于解决「回文子串」问题的另一种实现方式,其目标同样是计算字符串 s 中所有回文子串的数量。不同于之前的动态规划方法,这段代码采用了「中心扩展」策略,从每个可能的回文中心出发,向两边扩展以查找回文子串。

代码解析

  1. 初始化:

    • 首先检查字符串 s 是否非空,如果为空或长度小于1,直接返回0。
  2. 遍历回文中心:

    • 由于回文串可能有奇数长度或偶数长度,因此总共有 2 * len - 1 个潜在的回文中心点。遍历这 2 * len - 1 个中心点。
    • 对于每个中心点 i
      • 根据 i 的奇偶性确定中心的左右位置。如果 i 是偶数,则中心在 i/2i/2 + 1 之间(适用于偶数长度的回文串),如果 i 是奇数,则中心在 i/2(适用于奇数长度的回文串)。
      • 初始化左右指针 leftright,它们分别指向回文中心的两侧。
  3. 扩展并检查回文:

    • 从当前中心点开始,向两边扩展,同时检查两边的字符是否相等。
    • 如果两边的字符相等,将 ans(回文子串数量)加1,并继续向两边扩展。
    • 当两边的字符不相等或左右指针越界时,停止当前的扩展过程,转向下一个中心点。
  4. 返回结果:

    • 最后返回 ans,即字符串 s 中所有回文子串的数量。

时间复杂度和空间复杂度

  • 时间复杂度: O(n^2),其中 n 是字符串 s 的长度。虽然每次扩展可能只涉及线性时间,但由于需要从每个可能的中心点开始扩展,总的时间复杂度为 O(n^2)。
  • 空间复杂度: O(1),除了输入字符串 s,代码中没有使用额外的数据结构。

总结

这段代码通过「中心扩展」的方法,有效地解决了回文子串计数问题。与动态规划方法相比,这种方法不需要额外的存储空间,且代码实现更为直观,容易理解。在处理回文子串计数问题时,「中心扩展」策略是一种常见的有效且高效的算法。不过,当字符串长度非常大时,其 O(n^2) 的时间复杂度可能会成为性能瓶颈,这时可能需要考虑更高级的算法或数据结构,如Manacher算法,以获得更好的时间复杂度。

516. 最长回文子序列

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

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

示例 1:

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

输入:s = “cbbd”
输出:2
解释:一个可能的最长回文子序列为 “bb” 。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

public class Solution {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int[][] dp = new int[len + 1][len + 1];
        for (int i = len - 1; i >= 0; i--) { // 从后往前遍历 保证情况不漏
            dp[i][i] = 1; // 初始化
            for (int j = i + 1; j < len; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], Math.max(dp[i][j], dp[i][j - 1]));
                }
            }
        }
        return dp[0][len - 1];
    }
}

这段代码是用于解决「最长回文子序列」问题的Java实现。给定一个字符串 s,目标是找到 s 中最长的回文子序列的长度。这里所说的“子序列”是指由原字符串中删除若干个字符(也可以不删除)后,保持剩余字符相对顺序不变所组成的新字符串。

代码解析

  1. 初始化动态规划数组:

    • 创建一个二维数组 dp,其大小为 (len + 1) x (len + 1),其中 len 是字符串 s 的长度。dp[i][j] 的值代表 s 中从下标 i 到下标 j 的子串中最长回文子序列的长度。额外的一行和一列是为了方便边界条件的处理。
  2. 动态规划迭代:

    • len - 10 反向遍历字符串 s 的每个字符,作为子串的起始点 i
    • 对于每个起始点 i,从 i + 1 开始到字符串的末尾遍历每个可能的结束点 j
    • 对于每一对起始点和结束点 ij
      • 如果 sij 位置的字符相等,那么 dp[i][j] 的值等于去掉这两个字符后子串的最长回文子序列长度加2,即 dp[i + 1][j - 1] + 2
      • 如果 sij 位置的字符不相等,那么 dp[i][j] 的值取 dp[i + 1][j]dp[i][j]dp[i][j - 1] 中的最大值,代表从 ij 的子串的最长回文子序列长度。
  3. 返回结果:

    • 最后返回 dp[0][len - 1],即整个字符串 s 的最长回文子序列的长度。

时间复杂度和空间复杂度

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

总结

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