d******4
发帖数: 132 | 1 Longest Palindromic Substring这一题. 同样的O(n^2)算法，java能过，python不能
过。
python exceeds time limit 了.
The following is java version:
public String longestPalindrome(String s) {
if(s == null || s.length()==0)
return "";
int maxLen = 0;
String res = "";
for(int i=0;i<2*s.length()-1;i++)
{
int left = i/2;
int right = i/2;
if(i%2==1)
right++;
String str = lengthOfPalindrome(s,left,right);
if(maxLen
{
maxLen = str.length();
res = str;
}
}
return res;
}
private String lengthOfPalindrome(String s, int left, int right)
{
while(left>=0 && right
{
left--;
right++;
}
return s.substring(left+1,right);
} | i***h
发帖数: 19 | 2 我也用python寫的，一開始試過各種O(n^2)方法都不行，估計預期是要manacher之類O(
n)的算法；不過我後來用一些trick把它給過了，主要是對於長字串和短字段分別處理
class Solution:
# @return a string
def longestPalindrome(self, s):
if s is None or len(s) == 0:
return ''
def max_palindrome(left, right, min_length):
if right - left < min_length:
return ''
start = left
while left < right:
if s[left] != s[right]:
if right - left < min_length:
return ''
start = left + 1
left += 1
right -= 1
length = (left - start) * 2 + (right - left + 1)
return s[start:start+length]
def is_palindrome(left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def get_max(left, cur_s, right, max_palin):
while left >= 0 and right < len(s) and s[left] == s[right]:
cur_s = s[left] + cur_s + s[right]
left -= 1
right += 1
return cur_s if len(cur_s) > len(max_palin) else max_palin
def process_short(max_palin):
for distance in xrange(half + 1):
for sign in (-1, 1):
i = half + sign * distance
# even palindrome
max_palin = get_max(i - 1, '', i, max_palin)
# odd palindrome
if i < len(s):
max_palin = get_max(i - 1, s[i], i + 1, max_palin)
max_half = min(i, len(s) - i)
if len(max_palin) == max_half * 2:
return max_palin
return max_palin
half = len(s) / 2
if len(s) <= 300:
return process_short(s[0])
if is_palindrome(0, len(s) - 1):
return s
max_palin = ''
for i in range(1, half):
if is_palindrome(i, len(s) - 1) and len(s[i:len(s)]) > len(max_
palin):
max_palin = s[i:len(s)]
for j in range(half, len(s) - 1):
if is_palindrome(0, j) and len(s[:j + 1]) > len(max_palin):
max_palin = s[:j + 1]
if not max_palin:
cur_max = self.longestPalindrome(s[:half])
if len(cur_max) > len(max_palin):
max_palin = cur_max
cur_max = self.longestPalindrome(s[half:])
if len(cur_max) > len(max_palin):
max_palin = cur_max
if len(max_palin) >= half:
return max_palin
return process_short(max_palin) | d******4
发帖数: 132 | 3 That's great. But it's hard to figure out the way in interview.
O(
【在 i***h 的大作中提到】
: 我也用python寫的，一開始試過各種O(n^2)方法都不行，估計預期是要manacher之類O(
: n)的算法；不過我後來用一些trick把它給過了，主要是對於長字串和短字段分別處理
: class Solution:
: # @return a string
: def longestPalindrome(self, s):
: if s is None or len(s) == 0:
: return ''
: def max_palindrome(left, right, min_length):
: if right - left < min_length:
: return ''
| l***s
发帖数: 15 | 4 my accepted codes. seems different algorithm than the one found online
class Solution:
# @return a string
def longestPalindrome(self, s):
le = len(s)
if not s:
return ''
table=[] #record longest so far and longest ending at i
table.append(((0,0), 1))
for i in xrange(1,le):
curind=table[-1][0]
lastsofar=curind[1]-curind[0]+1
lastending=table[-1][1]
for j in xrange(i-lastending-1, i+1):
if j<0:
continue
elif self.isPalindrome(s[j:i+1]):
curending=i-j+1
if curending>lastsofar:
curind=(j, i)
table.append((curind, curending))
break
curind=table[-1][0]
return s[curind[0]:curind[1]+1]
def isPalindrome(self, s):
le = len(s)
i=0
j=le-1
if le<=1:
return True
while i
while not s[i].isalnum():
i+=1
if i>=j:
return True
while not s[j].isalnum():
j-=1
if i>=j:
return True
if s[i] != s[j] and abs(ord(s[i])-ord(s[j])) !=32:
return False
else:
i+=1
j-=1
return True
【在 d******4 的大作中提到】
: Longest Palindromic Substring这一题. 同样的O(n^2)算法，java能过，python不能
: 过。
: python exceeds time limit 了.
: The following is java version:
: public String longestPalindrome(String s) {
: if(s == null || s.length()==0)
: return "";
: int maxLen = 0;
: String res = "";
: for(int i=0;i<2*s.length()-1;i++)
| D****3
发帖数: 611 | 5
其实这个java解本身就不是最优的。因为跑了很多根本没可能是最长susbtring的解。
Leetcode对python的速度比较高。我在你的算法上改进了下：
从中间开始选对称轴，向两边移动。当剩下的最长可能palindrome substring都没当前
最长的palindrome subtring长的时候，立刻返回当前最长的解。
【在 d******4 的大作中提到】
: Longest Palindromic Substring这一题. 同样的O(n^2)算法，java能过，python不能
: 过。
: python exceeds time limit 了.
: The following is java version:
: public String longestPalindrome(String s) {
: if(s == null || s.length()==0)
: return "";
: int maxLen = 0;
: String res = "";
: for(int i=0;i<2*s.length()-1;i++)
| D****3
发帖数: 611 | 6
我原来给的解还能refactor一下。给个新的吧：
--------
其实这个java解本身就不是最优的。因为跑了很多根本没可能是最长susbtring的解。
Leetcode对python的速度比较高。我在你的算法上改进了下：
从中间开始选对称轴，向两边移动。当剩下的最长可能palindrome substring都没当前
最长的palindrome subtring长的时候，立刻返回当前最长的解。
class Solution:
def longestPalindrome(self, s):
longest, mid = "", (len(s) - 1) / 2
i, j = mid, mid
while i >= 0 and j < len(s):
args = [(s, i, i), (s, i, i + 1), (s, j, j), (s, j, j + 1)]
for arg in args:
tmp = self.longestPalindromeByAxis(*arg)
if len(tmp) > len(longest):
longest = tmp
if len(longest) >= i * 2:
return longest
i, j = i - 1, j + 1
return longest
def longestPalindromeByAxis(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left, right = left - 1, right + 1
return s[left + 1 : right]
---
source: https://github.com/jw2013/Leetcode/
【在 d******4 的大作中提到】
: Longest Palindromic Substring这一题. 同样的O(n^2)算法，java能过，python不能
: 过。
: python exceeds time limit 了.
: The following is java version:
: public String longestPalindrome(String s) {
: if(s == null || s.length()==0)
: return "";
: int maxLen = 0;
: String res = "";
: for(int i=0;i<2*s.length()-1;i++)
|
|
