leetcode5-最长回文子串

原题

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例1:

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

示例2:

输入: "cbbd"
输出: "bb"

解法

思想

以每个字符或两个字符中间的位置为中心向两边延申看能达到两边对称的最大长度,如果超过记录的最大长度就把start和end位置记录下来,最后根据start和end返回对应的子字符串。

代码

class Solution {
    int start = 0;
    int end = 0;
    char[] chars;
    public String longestPalindrome(String s) {
        if(s.equals("")) return "";
        chars = s.toCharArray();
        for(int i = 0;i<chars.length-1;i++){
            expandLength(i,i);
            expandLength(i,i+1);
        }
        return s.substring(start,end+1);
    }

    public void expandLength(int left,int right){
        if(chars[left] != chars[right]) return;
        while(left!=0&&right!=chars.length-1&&chars[left-1] == chars[right+1]){
            left--;
            right++;
        }
        if(right-left>end-start){
            start = left;
            end = right;
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode5-%e6%9c%80%e9%95%bf%e5%9b%9e%e6%96%87%e5%ad%90%e4%b8%b2/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月19日
下一篇 2020年2月20日

相关推荐

  • leetcode67-二进制求和

    原题 给定两个二进制字符串,返回他们的和(用二进制表示)。 输入为非空字符串且只包含数字 1 和 0。 示例 1: 输入: a = “11”, b = “1” 输出: “100” …

    算法 2019年11月15日
    0100
  • leetcode145-二叉树的后序遍历

    原题 给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3]  1   \    2 &nbs…

    算法 2020年1月10日
    080
  • leetcode104-二叉树的最大深度

    原题 给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例:给定二叉树 [3,9,20,null…

    算法 2020年1月11日
    090
  • 剑指offer05-替换空格

    原题(来源Leetcode) 请实现一个函数,把字符串 s 中的每个空格替换成"%20"。 示例1: 输入: s = "We are happy." 输出: "We%20are%2…

    算法 2020年4月5日
    0110
  • 程序员面试金典01.07-旋转矩阵

    原题(来源Leetcode) 给你一幅由 N × N 矩阵表示的图像,其中每个像素的大小为 4 字节。请你设计一种算法,将图像旋转 90 度。 不占用额外内存空间能否做到? 示例 …

    算法 2020年4月7日
    0410
  • leetcode289-生命游戏

    原题 根据 百度百科 ,生命游戏,简称为生命,是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。 给定一个包含 m × n 个格子的面板,每一个格子都可以看成是一个细胞…

    算法 2020年4月2日
    0300
  • leetcode295-数据流的中位数

    原题 中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。 例如, [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.…

    算法 2020年2月12日
    0110
  • leetcode79-单词搜索

    原题 给定一个二维网格和一个单词,找出该单词是否存在于网格中。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格…

    算法 2020年4月12日
    0130
  • leetcode704-二分查找

    原题 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示…

    算法 2019年12月29日
    080
  • leetcode1013-将数组分成和相等的三个部分

    原题 给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。 形式上,如果可以找出索引 i+1 < j 且满足 (A[0] +…

    算法 2020年3月11日
    0560

发表回复

登录后才能评论