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.
寻找最长的回文字符串。用的是一个比较简单的方式。即每一个字符开始比较它之前和之后的字符来判断是否为相同,若相同,则继续向前,向后比较,直至到不相同。判断回文字符串的长度是否更长。
public class Solution {
public String longestPalindrome(String s) {
String str = "";
int midIndex = 0 ;
int num = 0 ;
boolean isOnly = false;
for(int i = 0;i<s.length()-1;i++){
if(s.length()-1 - i < num){
break;
}else{
if(s.charAt(1+i) == s.charAt(i)){
int j = 1;
while(i-j>=0&&i+j+1<s.length()&&s.charAt(i-j) == s.charAt(i+j+1)){
j++;
}
if(num < j){
num = j;
midIndex = i;
isOnly = false;
}
}
if(i!= 0&&s.charAt(1+i) == s.charAt(i-1)){
int j = 1 ;
while(i-j>=0&&i+j<s.length()&&s.charAt(i+j) == s.charAt(i-j)){
j++;
}
j--;
if(num <= j){
num = j;
midIndex = i;
isOnly = true;
}
}
}
}
if(num ==0){
str = s.charAt(0)+"";
}else if(isOnly){
str = s.substring(midIndex - num, midIndex + num+1);
}else{
str = s.substring(midIndex- num+1,midIndex +num +1) ;
}
return str;
}
}
寻找最长的回文字符串。用的是一个比较简单的方式。即每一个字符开始比较它之前和之后的字符来判断是否为相同,若相同,则继续向前,向后比较,直至到不相同。判断回文字符串的长度是否更长。
public class Solution {
public String longestPalindrome(String s) {
String str = "";
int midIndex = 0 ;
int num = 0 ;
boolean isOnly = false;
for(int i = 0;i<s.length()-1;i++){
if(s.length()-1 - i < num){
break;
}else{
if(s.charAt(1+i) == s.charAt(i)){
int j = 1;
while(i-j>=0&&i+j+1<s.length()&&s.charAt(i-j) == s.charAt(i+j+1)){
j++;
}
if(num < j){
num = j;
midIndex = i;
isOnly = false;
}
}
if(i!= 0&&s.charAt(1+i) == s.charAt(i-1)){
int j = 1 ;
while(i-j>=0&&i+j<s.length()&&s.charAt(i+j) == s.charAt(i-j)){
j++;
}
j--;
if(num <= j){
num = j;
midIndex = i;
isOnly = true;
}
}
}
}
if(num ==0){
str = s.charAt(0)+"";
}else if(isOnly){
str = s.substring(midIndex - num, midIndex + num+1);
}else{
str = s.substring(midIndex- num+1,midIndex +num +1) ;
}
return str;
}
}
发表评论
-
Merge k Sorted Lists
2015-03-12 19:55 325Merge k sorted linked lists and ... -
Generate Parentheses
2015-03-12 19:50 363Given n pairs of parentheses, w ... -
Generate Parentheses
2015-03-05 22:39 0Given n pairs of parentheses, w ... -
Valid Parentheses
2015-03-05 22:33 307Given a string containing just ... -
Remove Nth Node From End of List
2015-03-05 22:31 339Given a linked list, remove the ... -
Letter Combinations of a Phone Number
2015-03-05 22:30 330Letter Combinations of a Phone ... -
4Sum
2015-03-05 22:26 311Given an array S of n integers, ... -
3Sum Closest
2015-03-05 22:25 291Given an array S of n integers, ... -
3Sum
2015-03-03 22:34 317Given an array S of n integers, ... -
Longest Common Prefix
2015-03-03 22:21 327Write a function to find the lo ... -
Roman to Integer
2015-03-03 22:20 326Given a roman numeral, convert ... -
Integer to Roman
2015-03-01 23:35 289Given an integer, convert it to ... -
Container With Most Water
2015-03-01 22:55 321Given n non-negative integers a ... -
Regular Expression Matching
2015-03-01 20:19 366Implement regular expression ma ... -
Palindrome Number
2015-02-13 22:08 330Determine whether an integer is ... -
String to Integer (atoi)
2015-02-13 11:07 341Implement atoi to convert a str ... -
Reverse Integer
2015-02-12 23:39 227Reverse digits of an integer. ... -
ZigZag Conversion
2015-02-12 23:37 254The string "PAYPALISHIRING ... -
Add Two Numbers
2015-02-12 22:12 300You are given two linked lists ... -
Longest Substring Without Repeating Characters
2015-02-11 21:14 425[size=24px;]Longest Substring W ...
相关推荐
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. ...
leetcode 分类leetcode ...Palindromic Substring 链表 #2:Add Two Numbers 分而治之 #53:Maximum Subarray 队列/集 #3:Longest Substring Without Repeating Characters 优先队列 #23:Merge k Sorted Lists
Palindromic Substring 中等 回文 ZigZag Conversion 中等 矩阵 重要 Reverse Integer 简单 字串 String to Integer (atoi) 中等 字串 麻烦 Palindrome Number 简单 字串 Container With Most Water 中等 动态规划 ...
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 006. ZigZag Conversion 007. Reverse Integer 008. String to Integer 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 中等 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 ...
Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7.Reverse Integer 8.String to Integer (atoi) 9.Palindrome Number 10.Regular Expression Matching 11.Container With Most Water 12.Integer ...
Palindromic Substring 20.Valid Parentheses 26.Remove Duplicates from Sorted Array 53.Maximum Subarray 70.Climbing Stairs 121.Best Time to Buy and Sell Stock 122.Best Time to Buy and Sell Stock II 123....
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
Palindromic Substring [Medium] LC5: Median Of Two Sorted Arrays [Hard] LC6: Zigzag Conversion [Medium] LC7: Reverse Integer [Easy] LC8: String To Integer Atoi [Medium] LC9: Palindrome Number [Easy] LC...
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 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 ...
Palindromic Substring 最长回文子串 string,dp 8 String to Integer(atoi) 字符串转整数 string 13 Roman to Integer 罗马数字转整数 number,string 14 Longest Common Prefix 最长公共前缀 string 16 3Sum Closest...
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 ...
leetcode信封 ...Palindromic Substring │ RansomNote.java //383. Ransom Note │ RussianDollEnvelope.java //354. Russian Doll Envelopes │ SlidingWindowMaximum.java //239. Sliding Window Maximum
Palindromic Substring Interleaving String Triangle Distinct Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container With Most Water 盛最多水的容器 13 Roman to Integer 罗马数字转整数 14 Longest Common Prefix 最长...