美文网首页
647.回文子串

647.回文子串

作者: 一角钱技术 | 来源:发表于2020-08-20 11:19 被阅读0次

    647.回文子串

    给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。
    具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

    
    示例 1:
    输入:"abc"
    输出:3
    解释:三个回文子串: "a", "b", "c"
        
    示例 2:
    输入:"aaa"
    输出:6
    解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
    

    提示:
    输入的字符串长度不会超过 1000 。

    参考思路

    1. 定义状态

    dp[i][j] 表示从位置 i 到 j 上的字符串是否为回文串,例如: i = 0, j = 1 表示字符串ab,则dp[0][1] = false

    2. 状态转移(DP方程)

    对于 i 到 j 上的位置的字符串,如果 s[i] == s[j] 且满足以下几点,则为回文串

    • i 与 j 的距离 <= 2, 则为回文串。例如 aa 、aba 均为回文串
    • i 与 j 的距离 > 2, 且 dp[i+1][j-1] == true, 则为回文串。例如 abccba, i+1 —> j-1 的字符串为 bccb,其为回文串

    3. 定义边界

    i 从字符串末尾依次向头移动,判断以 i 字符开头,以 s.length() - 1 结尾结束的字符串之间存在的回文串树,因此 j 每次从字符串尾开始移动,知道 i == j,结束一轮比较。

    参考代码1

    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        // dp[i][j] 表示第i个字符到第j个字符是否为回文串
        boolean[][] dp = new boolean[n][n];
        int count = 0;
        // 依次以i开头的字符串,判断从i j 之间是否有回文串
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = s.length() -1; j >= i; j--) {
                 // dp[i][j] = (s[i] === s[j] && (j - i <= 2 || dp[i + 1][j - 1]))
                 if (s.charAt(i) == s.charAt(j) && (j - i <=2 || dp[i+1][j-1])) {
                     dp[i][j] = true;
                 }
                 if (dp[i][j]) {
                     count++;
                 }
             }
        }
        return count;
    }
    

    参考代码2

    class Solution {
        /**
        * 1.定义子问题
        *   字符串s[i...j]计算有多少个回文子串,可以分解成每个
        * 2.定义状态
        *   定义数组dp[i][j],表示字符串s[i...j]是否为回文字符串
        *   dp[i][j] = true,表示是回文子串
        *   dp[i][j] = false,表示不是回文子串
        * 3.DP方程
        *   (1)如果s[i] == s[j],那么说明只要dp[i+1][j-1]是回文子串,那么dp[i][j]也就是回问子串
        *   (2)如果s[i] != s[j],那么说明dp[i][j]必定不是回文子串
        */
        public int countSubstrings(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
            int n = s.length();
            boolean[][] dp = new boolean[n][n];
            int result = n;
            for (int i = 0; i < n; i++) {
                dp[i][i] = true;
            }
            for (int i = n - 1; i >= 0; i--) {
                for (int j = i + 1; j < n; j++) {
                    if (s.charAt(i) == s.charAt(j)) {
                        // j 和 i相邻的时候
                        if (j - i == 1) {
                            dp[i][j] = true;
                        } else {
                            dp[i][j] = dp[i+1][j-1];
                        }
                    } else {
                        dp[i][j] = false;
                    }
                    if (dp[i][j]) {
                        result++;
                    }
                }
            }
            return result;
        }
    }
    

    以上两个参考代码,时间复杂度:O(n^2),空间复杂度:O(n^2)

    参考代码3

    降维,空间复杂度优化为 O(n)
    把上图的表格横向压扁,竖向一列看作一维数组,还是原来的扫描方向。一维表格中的格子在迭代中更新

    class Solution {
        
        public int countSubstrings(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
            int n = s.length();
            boolean[] dp = new boolean[n];
            int count = 0;
            for (int i = 0; i < n; i++) {
                dp[i] = true;
                count++;
                for (int j = 0; j < i; j++) {
                    if (s.charAt(j) == s.charAt(i) && dp[j+1]) {
                        dp[j] = true;
                        count++;
                    } else {
                        dp[j] = false;
                    }
                }
            }
            return count;
        }
    }
    
    部分图片来源于网络,版权归原作者,侵删。
    

    相关文章

      网友评论

          本文标题:647.回文子串

          本文链接:https://www.haomeiwen.com/subject/huljjktx.html