文档章节

LeetCode题解-5-Longest Palindromic Substring

蔡晓建
 蔡晓建
发布于 2017/02/23 14:31
字数 243
阅读 1
收藏 0

解题思路

题目是查找最长的回文子串。

如果某个字符串是一个回文串,那么形式可能是cbabc,或cbaabc的形式,要找到最长的回文子串,可以以某个字符a开始,区分长度是奇数还是偶数,向左右两边一直比较,直到找到不同的字符。找到的字符就是以a为中心的最长回文子串。这样,只要遍历字符串,找到每个字符为中心的最长回文子串,就可以得到最终结果了。

参考源码

public class Solution {
    private String maxString = "";

    public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        int length = chars.length;
        for (int i = 0; i < length; i++) {
            // find longest odd palindrome
            findPalindrome(chars, length, i, 0);
            // find longest even palindrome
            findPalindrome(chars, length, i, 1);
        }
        return maxString;
    }

    private void findPalindrome(char[] chars, int length, int i, int shift) {
        int left = i;
        int right = i + shift;
        while (left >= 0 && right < length && chars[left] == chars[right]) {
            left--;
            right++;
        }
        if (right - left - 1 > maxString.length()) {
            maxString = new String(chars, left + 1, right - left - 1);
        }
    }
}

© 著作权归作者所有

共有 人打赏支持
蔡晓建
粉丝 10
博文 25
码字总数 9436
作品 0
广州
高级程序员
私信 提问
[leetcode] 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, and there exists one unique longest palindromic substring. ht......

jdflyfly
2014/06/24
614
0
[LeetCode] Longest Palindromic Substring

[LeetCode] Longest Palindromic Substring 题目 https://leetcode.com/problems/longest-palindromic-substring/ Given a string s, find the longest palindromic substring in s. You ma......

u013553529
2017/11/26
0
0
leetcode-algorithms-5 Longest Palindromic Substring

leetcode-algorithms-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......

mathli
11/22
0
0
leetcode算法题解(Java版)-2-最长回文子串

一、int数字反转 题目描述 Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 思路: 题目很简单,需要注意的是:int型是32位的。1000000003 ...

kissjz
04/28
0
0
5. Longest Palindromic Substring - LeetCode

LeetCode Problems Solutions question description: 问题描述 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. 给......

才华惊动党中央
2017/08/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

崛起于Springboot2.X之集成工作流Activiti5.22(42)

声明:该博客主要是Springboot1.X和Springboot2.X集成Activiti5.22版本,并说一下两个版本的搭建不同的地方 技术:Springboot2.0.3+mysql+jpa(自动生成25张表)+Activiti5.22 /然后Springboo...

木九天
5分钟前
0
1
windows环境下搭建rabbitMQ开发环境

windows环境下搭建rabbitMQ开发环境 下载与安装 erlang rabbitmq 是使用erlang语言开发的,所以需要erlang环境; 下载地址 rabbitmq 下载地址 rabbitmq与erlang版本关系 下载之后直接安装即可...

晨猫
17分钟前
0
0
JVM 中的守护线程

特点 通常由JVM启动 运行在后台处理任务,比如垃圾回收等 用户启动线程执行结束或者JVM结束时,会等待所有的非守护线程执行结束,但是不会因为守护线程的存在而影响关闭。 判断线程是否为守护...

小刀爱编程
20分钟前
1
0

参考 极客时间《数据结构与算法之美》

grace_233
33分钟前
2
0
谈谈KMP算法

KMP算法的资料网上已经一大把了,主要用来解决某个文本片段是否包含另一个子串问题。这里假设文本片段的长度n大于子串长度m,如: 文本串为ABCDABGHIJK 子串为 ABCDABE 在传统的暴力解法中当...

FAT_mt
35分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部