LeetCode第[5]题(Java):Longest Palindromic Substring 标签:String、动态规划
题目中文:求最长回文子串
题目难度:Medium
题目内容:
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
翻译:
给定一个字符串s,找出s中最长的回文子串。你可以假设s的最大长度是1000。
什么叫回文子串?
就是字符串中,满足能正读反读都一样的子串,就是回文子串。如下所示
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
我的思路:既然是特殊的子串那么,首先得得到每一个子串。然后用一个方法判定是否是回文,是的话就与答案长度做比较,更长则更新答案。
MyCode:
public String longestPalindrome(String s) {
int n = s.length();
String ans = "";
Set<String> set = new HashSet<String>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
set.add(s.substring(i, j));
}
}
for (String m : set) {
if (isPalindromic(m)) {
ans = m.length()>ans.length()?m:ans;
}
}
return ans;
} public boolean isPalindromic (String m) {
String reverse = new StringBuffer(m).reverse().toString();
return m.equals(reverse) ? true : false;
}
我的算法复杂度:O(N2)
结果不出意料:Time Limit Exceeded
编程过程中出现的问题:
1、因为最近在用python参加比赛,所以总是忘记定义变量类型。。。
2、一开始对回文子串理解错误,导致编程出错,所以啊,还是先看清题,理解题目意思再说;
3、String之间的比较一个手抖就直接用了“==”,哎 equals() 啊,我怎么总是对不起你。
然后傻呵呵地看答案去了…………
答案:
class Solution {
String ans = "";
public String longestPalindrome(String s) {
for (int i = 0;i < s.length(); i++) {
extendVerify(s,i,i);
extendVerify(s,i,i+1);
}
return ans;
}
public void extendVerify(String s, int j, int k) {
while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
j--;
k++;
}
String subString = s.substring(j+1,k);
ans = subString.length()>ans.length()?subString:ans;
}
}
答案算法复杂度:O(N)~ O(N2)
答案思路:分两部分,主方法对每个字符进行遍历,然后调用子方法由此字符出发向两边进行扩展,同时用两“指针”对左右的扩展字符进行比较,
调用两次子方法分别验证了以此字符为中心的左右的单数和双数的回文。
此代码还能优化:
1、主方法对s进行判断,如果长度小于2,即可直接返回s;
2、主方法的循环结束条件可以设置成 s.length - 1 , 因为最后一个没法往外扩展(但是0不能省,因为判断偶数扩展的时候必须是从(0,1)这两个开始);
3、子方法最后的更新其实只需要判断 j+1 到 k-1 的长度与 一个maxLen 的比较,然后再将 起始位置 j + 1,与长度 maxLen = k - j - 1 进行保存,就可以完成更新。
最新文章
- 【完全开源】Django多人博客系统——支持MarkDown和tinyMce
- 制作动画或小游戏——CreateJS基础类(一)
- jsp编程
- spring web MVC
- ACM/ICPC 之 拓扑排序范例(POJ1094-POJ2585)
- Maven学习3-使用Maven构建项目
- net 数据库连接详解 相当经典啊
- 初学android的第一个习作
- Redis 安装与简单示例 01_转
- WCF技术剖析之二:再谈IIS与ASP.NET管道
- Ubuntu 13.04设置root用户
- Oracle-11g-R2 于 Linux 上的 RAC 卸载
- where, group by, having
- 添加、设置tabBarItem属性
- js 正则学习小记之左最长规则
- eclipse-ee修改字体大小和配置Tomcat服务器
- Volley使用指南
- 使用scrapy爬虫,爬取17k小说网的案例-方法二
- 注解式controller开发,action找不到controller???
- postman-SSL证书问题-支持HTTPS请求
热门文章
- 超哥带你学网络编程部分blog
- Logon Session Times
- IO 之 File 类
- ubuntu14.04 编译安装CPU版caffe
- 【我的Android进阶之旅】Android调用JNI出错 java.lang.UnsatisfiedLinkError: No implementation found for的解决方法
- Java中Collections和Collection的区别
- python web框架 Django的APP以及目录介绍 django 1.11版本
- 基于mondrain 的原理纠正特殊指标值
- nfs服务、crond服务
- cdoj1329卿学姐与魔法