(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;elsereturn 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;elsereturn 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