【LeetCode Top 100】647. Palindromic Substrings【Medium】【JAVA】

╰半橙微兮° 2021-09-21 00:52 273阅读 0赞

## 1. 题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]

## 2. 题意 ##

题目比较好理解，即计算出有多少个回文子串，同时**位置不同的相同回文子串，将被视为两个**。

## 3.方法一 ##

### 3.1 思路 ###

因为位置不同的回文子串需要被重复计数，比较简单的想法，就是将所有的可能的组合都列出来，并判断每一种是否是回文子串。这样代码思路比较简单，但运行时间一定是较长，根据这个思路可再进一步简化。  
对于回文子串的判断，我们一般简单的办法是从中间向两边进行扩展，即对于a,b,c,b,a，如果拿单个c的时候，我们判断为回文子串，此时将其左右纳入，即bcb的子串，再判断也为回文子串，则再将左右纳入，即abcba的子串，这个思路与前面将所有情况都列举的思路实质上相同，只是我们可以通过一定的方法减少部分情况的判断。思路教简单，下面是该思路的代码。

### 3.2 代码 ###

public int countSubstrings(String s) { 
            int num = 0;
            char[] a = s.toCharArray();
            // 注意，这里需根据子串长度的奇偶分两种情况
            for (int i = 0; i < s.length(); i++) { 
                num += count(a, i, i);
                num += count(a, i, i + 1);
            }
            return num;
        }
    
        private int count(char[] a, int left, int right) { 
            int num = 0;
            // 当某个子串是回文子串时，向左右两侧扩展，直至不再是回文子串或超过数据越界
            while (left >= 0 && right < a.length && a[left] == a[right]) { 
                num++;
                left--;
                right++;
            }
            return num;
        }

### 3.3 运行结果 ###

![在这里插入图片描述][20191219000651546.png]

## 4 方法二 ##

### 4.1 思路 ###

这道题也可以使用动态规划的思路进行解答，思路其实类似思路一，只是写成动态规划的思路。假设\[i,j\]表示从第i位置到第j位置的子串，那么我们要判断\[i,j\]是回文子串时，根据思路一的思路，我们需要判断两个条件：①\[i+1,j-1\]是回文子串 ②i位置的字符与j位置的字符相同。演变成动态规划那种写法就是：`dp[i][j]` 为true的条件是：`dp[i+1][j-1] == true && s[i] == s[j]`。

### 4.2 代码 ###

public int countSubstrings1(String s) { 
            if (s == null) { 
                return 0;
            }
            int num = 0;
            
            // dp[i][j]为true代表：以下标i为起点，下标j为终点的子串为回文子串
            boolean dp[][] = new boolean[s.length()][s.length()];
            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 <= 2) || (dp[i + 1][j - 1]))) { 
                        dp[i][j] = true;
                        num++;
                    }
                }
            }
            return num;
        }

### 4.3 运行结果 ###

![在这里插入图片描述][20191219224504713.png]

## 5. 相关链接 ##

[本题代码的github链接][github]  
[其他 LeetCode 题目解析][LeetCode]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/83538a25945246bbb0f64dba2fe28a1d.png
[20191219000651546.png]: /images/20210920/2eec417aa17b4ad58dbbeb88bb9492e3.png
[20191219224504713.png]: /images/20210920/d261e0b773b94b8f85e4010340c0924d.png
[github]: https://github.com/Parallelline1996/Leetcode/blob/master/Problems/src/main/java/page7/N647_PalindromicSubstrings.java
[LeetCode]: https://blog.csdn.net/applying/category_9629399.html