(Longest Palindromic Substring)
source link: https://tianrunhe.wordpress.com/2012/07/29/longest-palindromic-substring/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
(Longest Palindromic Substring)
29 Jul 2012 5 Comments
by Runhe Tian in LeetCode Tags: C++, Java, Recursion, String
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.
Thoughts:
Two parts of this question: determine if a string is palindrome and find out the longest palindrome. First part can be done in recursive or iterative way. We just need to check if the 1st letter == last letter, 2nd letter == 2nd last letter, so on and so forth. Second part we can do it using a sliding window approach. We examine if the entire string is palindrome or not, then the substrings of length n – 1 (there are two of them), then the substrings of length n – 2 (3 of them), etc.
Code (Java):
public
class
Solution {
public
String longestPalindrome(String s) {
for
(
int
len = s.length(); len >
0
; --len) {
for
(
int
j =
0
; j <= s.length() - len; ++j) {
String sub = s.substring(j, j + len);
if
(isPalindrome(sub))
return
sub;
}
}
return
new
String();
}
private
boolean
isPalindrome(String s) {
if
(s.length() <=
1
)
return
true
;
else
return
s.charAt(
0
) == s.charAt(s.length()-
1
) &&
isPalindrome(s.substring(
1
,s.length()-
1
));
}
}
Code (C++):
class
Solution {
public
:
string longestPalindrome(string s) {
for
(
int
len = s.size(); len > 0; --len) {
for
(
int
i = 0; i <= s.size() - len; ++i) {
string sub = s.substr(i, len);
if
(isPalindrome(sub))
return
sub;
}
}
return
""
;
}
private
:
bool
isPalindrome(string s) {
if
(s.size() <= 1)
return
true
;
else
return
s[0] == s[s.size() - 1] &&
isPalindrome(s.substr(1,s.size()-2));
}
};
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK