文档章节

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);
        }
    }
}

© 著作权归作者所有

共有 人打赏支持
蔡晓建
粉丝 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
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算法题解(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
【DSAA】Longest Palindromic Substring

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

jiantao88
01/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Qt编写自定义控件属性设计器

以前做.NET开发中,.NET直接就集成了属性设计器,VS不愧是宇宙第一IDE,你能够想到的都给你封装好了,用起来不要太爽!因为项目需要自从全面转Qt开发已经6年有余,在工业控制领域,有一些应用...

飞扬青云
33分钟前
1
0
我为什么用GO语言来做区块链?

Go语言现在常常被用来做去中心化系统(decentralised system)。其他类型的公司也都把Go用在产品的核心模块中,并且它在网站开发中也占据了一席之地。 我们在决定做Karachain的时候,考量(b...

HiBlock
39分钟前
1
0
大数据学习脑图以及入门教程!

近些年,大数据的火热可谓是技术人都知道啊,很多人呢,也想学习大数据相关,所以,这里分享几个大数据脑图,希望可以让你清楚明白从哪里入门大数据,知道该学习以及掌握哪些知识点; 大数据...

董黎明
今天
1
0
聊聊redis的监控工具

序 本文主要研究一下redis的监控工具 redis-stat redis-stat是一个比较有名的redis指标可视化的监控工具,采用ruby开发,基于redis的info命令来统计,不影响redis性能。 docker运行 docker r...

go4it
今天
2
0
TypeScript基础入门之高级类型的索引类型(Index types)

转发 TypeScript基础入门之高级类型的索引类型(Index types) 高级类型 索引类型(Index types) 使用索引类型,编译器就能够检查使用了动态属性名的代码。 例如,一个常见的JavaScript模式是从...

durban
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部