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++)
|
|