[LeetCode]005. Longest Palindromic Substring
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.
Solutions: use DP, find the base cases: "a", "bb", and then create the common method.
(Reference:http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html)
Running time: O(n*n). (while the brute force method can cause O(n*n*n)) running time.
Space: O(n*n).
これはLeetCodeで出会った最初のDPのテーマで、いつDPを使うかについて私の理解はまだ浅いです.
1.サブ問題は繰り返し呼び出すことができる.
2.最適サブ問題がある.
次の問題を解く過程でDPを深く理解する必要がある.
3/24/2015 Updated
Python Solution: divide palindrome into two types: original from "a"or "aa".
Running Time: O(n*n)
Solutions: use DP, find the base cases: "a", "bb", and then create the common method.
(Reference:http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html)
Running time: O(n*n). (while the brute force method can cause O(n*n*n)) running time.
Space: O(n*n).
これはLeetCodeで出会った最初のDPのテーマで、いつDPを使うかについて私の理解はまだ浅いです.
1.サブ問題は繰り返し呼び出すことができる.
2.最適サブ問題がある.
次の問題を解く過程でDPを深く理解する必要がある.
public class Solution {
public String longestPalindrome(String s) {
// Start typing your Java solution below
// DO NOT write main() function
int n = s.length();
boolean[][] table = new boolean[1000][1000];
int s_start = 0;
int maxLength = 1;
//use a char[] for convenience, can also use s.charAt(i) for saving space.
char[] s1 = s.toCharArray();
//base case1: a is a palindrome;
for(int i=0; i<n; i++){
table[i][i] = true;
}
//base case2: aa is also a palindrome;
for(int i=0; i<n-1; i++){
if(s1[i] == s1[i+1]){
table[i][i+1] = true;
maxLength = 2;
s_start = i;
}
}
//other cases: maxLength from 3 to n;
for(int len=3; len<=n; len++){
for(int i=0; i<n-len+1; i++){
int j = i+len-1;
if(s1[i]==s1[j] && table[i+1][j-1]){
table[i][j] = true;
maxLength = len;
s_start = i;
}
}
}
return s.substring(s_start, s_start+maxLength);
//substring method: begin index---inclusive; end index---exclusive;
}
}
3/24/2015 Updated
Python Solution: divide palindrome into two types: original from "a"or "aa".
Running Time: O(n*n)
class Solution:
# add a helper function to get the longest Palindrome in a specific position. |left right|
def getLongestPalindrome(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left+1:right]
# @return a string
def longestPalindrome(self, s):
palindrome = ""
for i in range(len(s)):
singlePalindrome = self.getLongestPalindrome(s, i, i)#from the type "a"
if len(singlePalindrome) > len(palindrome):
palindrome = singlePalindrome
doublePalindrome = self.getLongestPalindrome(s, i, i+1)#from the type "aa"
if len(doublePalindrome) > len(palindrome):
palindrome = doublePalindrome
return palindrome