【LeetCode】5. Longest Palindromic Substring

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

分析

首先需要知道什么是回文,我们称正读和反读都相同的字符序列为回文,如“abba”、“abccba”、12321、123321是“回文”,“abcde”和“ababab”则不是“回文”。那么一个回文是一个中心对称的,可以使用中心扩散的方法去查找方法,但是需要考虑到中心是奇数个字母还是偶数个字母。那么程序方式就是一个循环,每到字符,就对当前字符进行中心扩散查找回文内容,然后去比较回文的长度。

程序实现

public class LongestPalindromicSubstring {
    String res = "";    // 结果
    public String longestPalindrome(String s) {
        if( s == null || s.length() == 0) return s;
        for (int i = 0; i< s.length();i++){
            helper(s, i, i);       // 中心为奇数
            helper(s, i, i + 1);   // 中心为偶数
        }
        return res;
    }

    /**
     * @param s :需要查找的字符串
     * @param left : 向左扩散的初始索引
     * @param right : 向右扩散的初始索引
     */
    public void helper(String s, int left, int right){
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right) ){
            left -- ; // 向左扩散
            right ++ ; // 向右扩散
        }
        // 比较当前回文长度,结果替换
        if(s.substring(left +1,right).length()>res.length()) res = s.substring(left +1,right);
    }
    @Test
    public void test(){
        LongestPalindromicSubstring lps = new LongestPalindromicSubstring();
        System.out.println(lps.longestPalindrome("abbacdeedc"));;
    }
}

个人订阅号

第一个订阅号侧重于:使用c/c++/java去实现一些经典算法,以及javaEE开发,Linux服务器操作等。第二个订阅号主要侧重于机器学习,深度学习,数学,自然语言处理等方面的知识。







 上一篇
如何使用python将多个png图片转为gif 如何使用python将多个png图片转为gif
前言最近遇到一个问题是,画了一个过程的图,为了更生动地展示出来,于是就想把这几张图合成一个gif图片,这样起来应该是不错的,于是在网上搜索了一些关于python如何将一些png图片转为gif的程序,自己实现更改如下。 环境准备系统:win1
2019-01-27
本篇 
【LeetCode】5. Longest Palindromic Substring 【LeetCode】5. Longest Palindromic Substring
题目Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Ex
2019-01-27
  目录