文档章节

LeetCode题解-5-Longest Palindromic Substring

蔡晓建
 蔡晓建
发布于 2017/02/23 14:31
字数 243
阅读 1
收藏 0
点赞 0
评论 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);
        }
    }
}

© 著作权归作者所有

共有 人打赏支持
蔡晓建
粉丝 8
博文 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 ⋅ 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

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

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

【DSAA】Longest Palindromic Substring

最近刷LeetCode遇到一个比较有意思的题目(Longest Palindromic Substring),求一个字符串的最大回文子串。题目本身并不难,但需要理清思路才好理解,借此文记录下。 题目 Given a string s...

jiantao88 ⋅ 01/04 ⋅ 0

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", whic......

jdflyfly ⋅ 2014/06/24 ⋅ 0

leetcode-java题解(每天更新)

说明:选用java,重在体会,性能不是最优。欢迎转载:http://www.ming-yue.cn/leetcode-java-solutions/。 先给出一个leetcode的已有答案,为什么上来直接给出答案,因为这个好多答案写的都非...

韩来明 ⋅ 2015/03/09 ⋅ 0

leetcode刷题,没想到这么难搞!

leetcode之前提交的代码不见了,所以在这里记一下 https://leetcode.com/problems/longest-substring-without-repeating-characters/...

fromdtor ⋅ 2016/10/13 ⋅ 0

Palindromic SubString(回文字符串)

回文字符串 求解判断回文字符串 取一个字符串中最长的回文串 方法3.manacher算法 这里有个讲解 leetcode上的英文说明大概意思就是在原有的字符串基础上重新插入一个特殊的字符#,重新构建一个...

Cobbage ⋅ 2016/12/19 ⋅ 0

LeetCode Question Difficulty Distribution 问题难度和频率分布

Leetcode问题难度和频率分布表 引用自: https://zephyrusara.blogspot.jp/2014/07/leetcode-question-difficulty.html LeetCode Question Difficulty Distribution : Sheet1......

xidiancoder ⋅ 2017/09/10 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

开启Swarm集群以及可视化管理

在搭建的两台coreos服务器上开启swarm集群 前置条件: docker均开启2375端口 同一个局域网内 主服务器上安装Portainer容器 安装Portainer容器执行: docker run -d -p 9000:9000 --restart=a...

ykbj ⋅ 14分钟前 ⋅ 0

单例设计模式

1、单例模式确保某一个类只有一个实例,而且自行实例化并向整个系统提供这个实例 2、饿汉式单例类 在这个类被加载时,静态变量instance会被初始化,此时类的私有构造子会被调用 饿汉式是典型...

职业搬砖20年 ⋅ 19分钟前 ⋅ 0

前端基础(四):前端国际规范收集

字数:1142 阅读时间:5分钟 前言 由于前端技术的灵活性和杂乱性,导致网上的许多解决方案不够全面甚至是完全错误,容易起到误导作用。所以,我对搜索到的解决方案往往是存疑态度。那么,如何...

老司机带你撸代码 ⋅ 21分钟前 ⋅ 0

Failed to open/create Network-VirtualBox Host-Only

虚拟机版本 : Oracle Vm VirtualBox 5.2.12 报错时机:开网卡二,重启虚拟机报错 "Failed to open/create the internal network 'HostInterfaceNetworking-VirtualBox Host-Only Ethernet Ada......

p至尊宝 ⋅ 24分钟前 ⋅ 0

三分钟学会如何在函数计算中使用 puppeteer

摘要: 使用 puppeteer 结合函数计算,可以快速的构建弹性的服务完成各种功能,包括:生成网页截图或者 PDF、高级爬虫,可以爬取大量异步渲染内容的网页、模拟键盘输入、表单自动提交、登录网...

阿里云云栖社区 ⋅ 27分钟前 ⋅ 0

springMVC接收表单时 Bean对象有Double Int Char类型的处理

前台ajax提交表单price为double类型 后台controller就介绍不到 400错误 前台 实体类: public class ReleaseMapIconConfig{ private String id; private long maxValue; private long minVal......

废柴 ⋅ 30分钟前 ⋅ 0

ZOOKEEPER安装

工作需要在ubuntu上配置了一个zookeeper集群,有些问题记录下来。 1. zookeeper以来java,所以首先要安装java。但是ubuntu系统有自带的jdk,需要通过命令切换java版本: $ sudo update-alter...

恰东 ⋅ 32分钟前 ⋅ 0

linux 进程地址空间的一步步探究

我们知道,在32位机器上linux操作系统中的进程的地址空间大小是4G,其中0-3G是用户空间,3G-4G是内核空间。其实,这个4G的地址空间是不存在的,也就是我们所说的虚拟内存空间。 那虚拟内存空间...

HelloRookie ⋅ 33分钟前 ⋅ 0

myatis #{}与${}区别及原理

https://blog.csdn.net/wo541075754/article/details/54292751

李道福 ⋅ 36分钟前 ⋅ 0

三分钟学会如何在函数计算中使用 puppeteer

摘要: 使用 puppeteer 结合函数计算,可以快速的构建弹性的服务完成各种功能,包括:生成网页截图或者 PDF、高级爬虫,可以爬取大量异步渲染内容的网页、模拟键盘输入、表单自动提交、登录网...

猫耳m ⋅ 37分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部