寻找最长回文子串

最长回文子串

Posted by LY on February 14, 2019

在这里小小推荐下我的个人博客

csdn:雷园的csdn博客

个人博客:雷园的个人博客

简书:雷园的简书

前言

  1. 最近准备把算法慢慢的捡起来,所以准备日更一道算法题目,难度自然是由简入难,所以同学们可以每天都来看看小编的更新。
  2. 日更时间定在每晚20:00,希望大家多多关注啦。
  3. 昨天就欠更了,简直就是打脸。过完年刚开工,比较忙,今天更新两道,晚上还会更新一道!!!!!

寻找最长回文子串

给定一个字符串小号,发现最长的回文子小号。您可以假设s的最大长度为1000。

例1:

输入: “babad”
 输出: “bab”
 注意: “aba”也是一个有效的答案。

例2:

输入: “cbbd”
 输出: “bb”

解题思路

  1. 我们先说一下什么是回文串:简单的来说,回文串就是某一个字符串左右对称即为回文串。

  2. 那么回文子串也就是在某一字符串中,包含的回文串。

  3. 我们如何判断或者是寻找回文串呢?我们了解到他具有左右对称的性质,当我们要确认某一个字符串是否为回文串时,我们可以从字符串的中心开始,向左右两边进行对比。贴一段代码:

    // 验证是否为回文串
    private boolean check(String s, int j, int k) {
        // s:字符串 j:中心下标 k:中心下标。 
        // 当字符串长度为奇数时,j=k
        // 当字符串长度为偶数是,j=k-1
        while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
            j--;
            k++;
        }
        // 判断是否两边循环到了开始和结尾。
        if(j==0&&k==s.length()-1){
            return true;
        }
        return false;
    }
    
  4. 那么寻找的方法也与上方代码大同小异。一起来看一下完整代码:

    public class Test {
        private int start=0; // 定义回文串开始下标
        private int maxLen=0; // 定义回文串最大长度
           
        @Test
        public void test(){
            // 输出答案
            System.out.println(longestPalindrome("babad"));
        }
           
        public String longestPalindrome(String s) {
            // 定义字符长度
            int len = s.length();
            // 判断长度如果小于2,即等于0或1,则直接返回当前字符串
            if (len < 2)
                return s;
            // 定义循环,即将i作为回文串的中心进行查找或验证。
            for (int i = 0; i < len - 1; i++) {
                // 假设答案回文串长度为奇数
                findPalindrome(s, i, i);  
                // 假设答案回文串长度为偶数
                findPalindrome(s, i, i + 1); 
            }
            // 从字符串中截取答案回文串
            return s.substring(start, start + maxLen);
        }
        // 查找回文串
        private void findPalindrome(String s, int j, int k) {
            // 以对称中心向左右比对字符以寻找回文串
            while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
                j--;
                k++;
            }
            //(k - j - 1)是本次查询获得的回文串长度
            if (maxLen < k - j - 1) {
                // 修改回文串开始下标
                start = j + 1;
                // 修改最大长度
                maxLen = k - j - 1;
            }
        }
    }
    

最后说两句

  1. 所有的题目都有很多种解法,我的一定不是最好的,甚至可以说是比较低端的解法,希望大牛们多多指教!!!
  2. 如果朋友们对算法、编程有很大兴趣的话,可以私信我,大家一同探讨;相互学习、共同进步。
  3. 朋友们如果对这道题目有更好的解法,希望可以在评论中指出,让大家一起讨论学习。
  4. 最后感谢大家的阅读以及关注,谢谢大家!!!