LeetCode算法题5----Longest Palindromic Substring
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, and there exists one unique longest palindromic substring.
算法分析
方法1
从最左边的字符(指标为 i )开始,从末尾寻找同该字符相同的字符(指标为 j ),然后依次比较 i++ 和 j-- 处的字符,如果相同,++i 和 --j,继续进行比较。直到 j<=i,说明当前考察的子字符串为 Palindromic;否则不是 Palindromic。
该方法的弊端就是太容易做无用功了:因为很可能出现两端字符依次相等而只有中间一小段的字符不相等的情况了。比如 "abcdefghigfedcba",只有比较到中间才会发现 h 和 i 不相等。
方法2
基于上述的问题,我们比较字符串的时候,从当前考察的子字符串的中间开始比较,因为 Palindromic 的字符串一定是镜像的,也就是说从中间向两端依次相等。我们可以从 i=0 到 i=s.length()-1 来遍历原字符串 s ,只要得出以 s.charAt(i) 为中间字符的字符串和以 s.charAt(i)与 s.charAt(i+1) 为中间两个字符的字符串的镜像长度,去二者最大者,就可以得出当前考察的 i 的镜像长度。
方法3
方法2是从 i=0 到 i=s.length()-1 来考察的,这回导致一些没必要的考察,因为很可能比较长的镜像字符串在中间位置,而较短的镜像字符串在边缘位置,这样,边缘的较短的镜像字符串根本就没必要去考察,所以,我们应该从字符串 s 的中间开始考察镜像字符串,如果出现了中间某个镜像字符串的的长度已经到达了字符串 s 的末端(即 s.charAt(0)或 s.charAt(s.length()-1) ),那么就可以知道当前考察的子字符串就是最长的镜像字符串了。
Java 算法实现
public class Solution {
public String longestPalindrome(String s) {
if(s==null){
return null;
}
int start=0,end=0;
int length=s.length();
int mid1=(length-1)>>>1;
int mid2=length>>>1;
int len=1,lenTmp;
if(mid1!=mid2){ //此时原字符串的长度一定为偶数
lenTmp=getLen(s, mid1, mid2);
if(lenTmp>len){
len=lenTmp;
start=mid1-((len>>1)-1);//len一定是偶数
end=mid2+((len>>1)-1);
}
}
int len1,len2;
for(int i=mid1,j=mid2;i>0&&j<length-1;i--,j++){
if(len>=((i<<1)+1)){
//接下来的长度已经不可能再比len更长了,没有比较的必要了
break;
}
len1=getLen(s, i, i);
len2=getLen(s, i-1, i);
lenTmp=Math.max(len1, len2);
if(lenTmp>len){
len=lenTmp;
start=i-(len>>>1);//i-((len-1)>>>1);
end=i+((len-1)>>>1);
if(len>=(i<<1)){
//已经达到最大长度,下面的长度就没有比较的必要了
return s.substring(start,end+1);
}
}
len1=getLen(s, j, j);
len2=getLen(s, j, j+1);
lenTmp=Math.max(len1, len2);
if(lenTmp>len){
len=lenTmp;
start=j-((len-1)>>>1);
end=j+(len>>>1);
if(len>=((length-j)<<1)){
//已经达到最大长度,下面的长度就没有比较的必要了
return s.substring(start,end+1);
}
}
}
return s.substring(start,end+1);
}
public int getLen(String s,int mid1,int mid2){
int L=mid1,R=mid2;
while(L>=0&&R<s.length()&&(s.charAt(L)==s.charAt(R))){
L--;
R++;
}
return (R-L-1);
}
}
最新文章
- Codeforces Round 319 # div.1 &; 2 解题报告
- Memcached【Magent+Memcached】集群
- [k]web页面-browser兼容问题-1
- LeetCode之Binary Tree Level Order Traversal 层序遍历二叉树
- submit异步提交 回调的方法
- SDUT 2623:The number of steps
- NOR Flash擦写和原理分析 (一)
- 关于使用base36的技巧 生成 优惠券兑换码的相关讨论
- 【转】小解DCT与DFT
- dubbox开发rest+json指南【转】
- SQLite: sqlite_master
- MySQL 数据库入门操作
- 微信QQ的二维码登录原理浅析
- Flex布局介绍
- React——共享state
- SSM-MyBatis-01:IDEA的安装,永久注册和简单的MyBatis用例
- java后台验证码工具
- Linux-父子进程的简单同步
- js原生事件系统与坐标系统
- properties文件读取工具类
热门文章
- 【转载】MDX Step by Step 读书笔记(四) - Working with Sets (使用集合)
- word中手动添加endnote的加载项
- 华南理工大学“三七互娱杯”程序设计竞赛 HRY and codefire(概率期望DP)
- Mac 10.12安装SVN工具SmartSVM 7.6
- tomcat无法登录
- First Android application
- R语言多元素向量
- PL/SQL:these query result are not updateable,include the ROWID to get updateab -----for update
- 一起来做Chrome Extension《搭个架子》
- Ruby(2): 基本语法上