409. 最长回文串

布满荆棘的人生 2023-07-17 04:52 40阅读 0赞

# 题目： #

[409. 最长回文串][409.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解： #

**0. 注意：**  
![在这里插入图片描述][20200319171939466.png]  
![在这里插入图片描述][20200319172009436.png]  
**1. 思路1：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20200319172543511.png]  
**2. 思路2：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]  
**3. 思路3：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]  
**4. 坑点：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]

# 代码： #

/** * code409 */
    public class code409 { 
    
        public static int longestPalindrome(String s) { 
            int a[] = new int[128];
            char C[] = s.toCharArray();
            // 因此要先数出给定字符串中各个字符的数量，这是第一个for循环完成的工作。
            for (int i = 0; i < C.length; i++) { 
                a[C[i]]++;
            }
            int count = 0;
            // 然后是把字符出现数量加起来，偶数次数的直接加，奇数次数的减一后再加。
            for (int i = 0; i < 128; i++) { 
                count += a[i] - a[i] % 2;
            }
            // 回文串的长度和s不相同，说明存在单个字符，把它加到最中间的位置，回文串长度+1。
            // 如果最终的长度小于原字符串的长度，说明里面某个字符出现了奇数次，那么那个字符可以放在回文串的最中间位置，所以额外再加一。
            if (count != s.length()) { 
                return count + 1;
            }
            // 回文串的长度和s相同，直接返回回文串长度。
            return count;
        }
    
        public static void main(String[] args) { 
            String s = "abccccdd";
            int res = longestPalindrome(s);
            System.out.println(res);
        }
    }

# 参考： #

1.  [最长回文串][Link 1]
2.  [Java的2种实现方法~][Java_2]
3.  [题本身没有什么难的，说几个容易出错的坑吧。][Link 2]
4.  [409. 最长回文串 双100%题解][409. _ _100]
5.  [图解回文串 C++ 超过了100%的提交][C_ _100]
6.  [Java toCharArray() 方法][Java toCharArray_]
7.  [ASCII][]

[409.]: https://leetcode-cn.com/problems/longest-palindrome/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: /images/20230528/510472ffea124451b4594ee479860b0c.png
[20200319171939466.png]: /images/20230528/c410258c6b4a4c3ca0ef4ccb12ad4e88.png
[20200319172009436.png]: /images/20230528/38eae36e7658465bbc2f5def50baf62d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/f2821edabe1c4b4bbb1f8243d6841e24.png
[20200319172543511.png]: /images/20230528/24a92089bcd14a43a5f96cca1e5c5ad2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 2]: /images/20230528/ec1db15959484a9793948e9320252ef6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 3]: /images/20230528/6cb0973f55e44d0282621914d81e5b0b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70 4]: /images/20230528/d545a626a83b4afcaa34e0a35c4b34b8.png
[Link 1]: https://leetcode-cn.com/problems/longest-palindrome/solution/zui-chang-hui-wen-chuan-by-leetcode-solution/
[Java_2]: https://leetcode-cn.com/problems/longest-palindrome/solution/javade-2chong-shi-xian-fang-fa-by-sweetiee/
[Link 2]: https://leetcode-cn.com/problems/longest-palindrome/solution/ti-ben-shen-mei-you-shi-yao-nan-de-shuo-ji-ge-rong/
[409. _ _100]: https://leetcode-cn.com/problems/longest-palindrome/solution/409-zui-chang-hui-wen-chuan-shuang-100ti-jie-by-yx/
[C_ _100]: https://leetcode-cn.com/problems/longest-palindrome/solution/tu-jie-hui-wen-chuan-by-time-limit/
[Java toCharArray_]: https://www.runoob.com/java/java-string-tochararray.html
[ASCII]: https://baike.baidu.com/item/ASCII