O(n^3)的程序:
public String longestPalindrome(String s) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int sMax=0,eMax=0,lMax=0;
int len=s.length();
for(int i=0;i<len-1;i++){
for(int k=0;i+k<len;k++){
int j=i+k;
int iTemp=i,jTemp=j;
while(s.charAt(iTemp)==s.charAt(jTemp)&&iTemp>=0&&jTemp>0&&jTemp>=iTemp){
iTemp++;
jTemp--;
}
if(iTemp>=jTemp){
if(k>lMax){
lMax=k;
sMax=i;
eMax=j;
}
}
}
}
return s.substring(sMax,eMax+1);
}
O(n^2):使用递归来做,使用dp[][]数组来构造动归,dp[i][j]表示以i为开头,以j为结尾的字符型是否为回文字符串,以k表示字符串长度,自k=1开始计算dp[i][i+k],随后k+1再算,知道计算出最后。在这个过程中,如果出现了回文字符串,将当前的k与之前的最大长度比较,如果大于,就更新最大长度以及起始点和终点。程序如下:
public String longestPalindrome(String s) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int maxL,maxS,maxE;
maxL=maxS=maxE=0;
int len=s.length();
boolean dp[][]=new boolean[len][len];
for(int i=0;i<len;i++){
for(int j=0;j<len;j++){
if(i>=j)
dp[i][j]=true;
else
dp[i][j]=false;
}
}
for(int k=1;k<len;k++){
for(int i=0;i<len;i++){
int j=i+k;
if(j>=len)
break;
if(s.charAt(i)==s.charAt(j)){
if(dp[i+1][j-1]||i>=len-1){
dp[i][j]=true;
if(k>maxL){
maxL=k;
maxS=i;
maxE=j;
}
}
}else{
dp[i][j]=false;
}
}
}
return s.substring(maxS,maxE+1);
}
此外,其他作者还写出有kmp匹配法以及一种名为
Manacher’sAlgorithm的算法,详情
http://blog.csdn.net/hopeztm/article/details/7932245
分享到:
相关推荐
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
Longest-Palindromic-Substring(最长回文子串) 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 Sample 1 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 Sample 2 输入...
最大公共字符串leetcode 最长回文子串 给定一个字符串 s,找出 s 中最长的回文子串。 您可以假设 s 的最大长度为 1000。 Example 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2: ...
leetcode 分类leetcode ...Palindromic Substring 链表 #2:Add Two Numbers 分而治之 #53:Maximum Subarray 队列/集 #3:Longest Substring Without Repeating Characters 优先队列 #23:Merge k Sorted Lists
最大公共字符串leetcode 最长回文子串 给定一个字符串 s,找出 s 中最长的回文子串。 您可以假设 s 的最大长度为 1000。 示例 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. 示例 2: ...
Palindromic Substring 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 12. Integer to Roman 13. Roman to Integer 14. Longest Common Prefix 15. 3Sum 20. Valid Parentheses 21. Merge...
Palindromic Substring 中等 6 ZigZag Conversion 中等 7 Reverse Integer 简单 8 String to Integer (atoi) 中等 9 Palindrome Number 简单 11 Container With Most Water 中等 12 Integer to Roman 中等 13 Roman ...
leetcode双人赛LeetCode 编号 题目 难度 题型 备注 Two Sum 简单 Add Two Numbers 中等 链结串列 重要 Longest Substring Without Repeating Characters 中等 字串 重要 Median of Two Sorted Arrays 困难 数学 ...
Palindromic Substring 006 ZigZag Conversion 007 Reverse Integer 008 String to Integer (atoi) 009 Palindrome Number 010 Regular Expression Matching 011 Container With Most Water 012 Integer to Roman ...
leetcode题库 ...Palindromic Substring 30.1% Medium 0006 ZigZag Conversion 37.5% Medium 0007 Reverse Integer 25.8% Easy 0008 String to Integer (atoi) 15.5% Medium 0009 Palindrome Number 49.4% Easy
Palindromic Substring 最长回文子串 string,dp 8 String to Integer(atoi) 字符串转整数 string 13 Roman to Integer 罗马数字转整数 number,string 14 Longest Common Prefix 最长公共前缀 string 16 3Sum Closest...
LeetCode刷题总结 1.Two Sum 2.Add Two Numbers 3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7....
leetcode信封 ...Palindromic Substring │ RansomNote.java //383. Ransom Note │ RussianDollEnvelope.java //354. Russian Doll Envelopes │ SlidingWindowMaximum.java //239. Sliding Window Maximum
Palindromic Substring 8 String to Integer 11 Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate ...
Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container With Most Water 盛最多水的容器 13 Roman to Integer 罗马数字转整数 14 Longest Common Prefix 最长...
Palindromic Substring 27.6% 中等 6 ZigZag Conversion 45.6% 中等 7 Reverse Integer 33.2% 简单 8 String to Integer (atoi) 18.5% 中等 9 Palindrome Number 56.7% 简单 10 Regular Expression Matching 25.3% ...
Palindromic Substring 6.ZigZag Conversion 7.Reverse Integer 8.String To Integer 9.Palindrome Number 10.String To Integer 11.Container With Most Water 12.Integer To Roman 13.Roman To Integer 289 347 ...
Palindromic Substring - 字数组余数:523. Continuous Subarray Sum - 无重复字符的最长子串:3. Longest Substring Without Repeating Characters - 最小跳跃步数问题 - 动态规划 + 循环策略优化:45. Jump Game ...
Palindromic Substring Interleaving String Triangle Distinct Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
java lru leetcode Leetcode-Java Use Java to solve Leetcode&JianZhiOffer ...Palindromic Substring (最长回文子串) Medium Dynamic Programming 7 Reverse Integer (整数反转) Easy Math 8 String to Integer (ato