Anyone pass the test in python?


  • 7
    J

    When I use Java, it just runs fine and passes the tests.
    But when I use the same algorithm in Python, it timesout every time.
    Got any idea?

    python code :

    def longestPalindrome(self, s):
            if len(s) == 0:
                return 0
            n = len(s)
            dp = [[False for i in xrange(n)] for j in xrange(n)]
            start = 0
            longest_len = 0
            for i in xrange(n):
                dp[i][i] = True
    
            for length in xrange(2,n+1):
                for i in xrange(0, n-length+1):
                    j = i+length-1
                    if s[i] == s[j] and (dp[i+1][j-1] or i+1>j-1):
                        dp[i][j] = True
                        if length > longest_len:
                            longest_len = length
                            start = i
            return s[start:longest_len+1]
    

    java code:

    public String longestPalindrome(String s) {
            if(s==null||s.length()==1) return s;
            char[] str = s.toCharArray();
            boolean[][] bPald = new boolean[s.length()][s.length()];
            int start =0,end,maxLength=Integer.MIN_VALUE;
            for(int i=0;i<s.length();i++){
                bPald[i][i]=true;
            }
            for(int i=2;i<=s.length();i++){
                for(int j=0;j<s.length()-i+1;j++){
                    end = j+i-1;
                    if((str[j]==str[end]&&(bPald[j+1][end-1]||(j+1>end-1)))){
                        bPald[j][end]=true;
                        if(i>maxLength){
                            start=j;
                            maxLength = i;
                        }
                    }
                }
            }
            return s.substring(start,start+maxLength);
        }

  • 1
    K

    same question. O(n2) algo TLE with python


  • 0
    H

    Same with my c# and python

    c#

    public class Solution {
    	StringBuilder longPal = new StringBuilder();
    	public string LongestPalindrome(string s) {
    		if(s.Length<2) return s;
    		for(int i=0; i<s.Length; i++)
    		{
    			//Expand Even
    			LongestPalHelper(s, longPal, i, i);
    			LongestPalHelper(s, longPal, i, i+1);
    		}
    		return longPal.ToString();
    	}
    
    public void LongestPalHelper(string s, StringBuilder longPal, int i, int j)
    {
    	while(i>=0 && j<s.Length && s[i]==s[j])
    	{
    		if (j - i + 1 > longPal.Length) {
    			longPal.Clear();
    			
    			int endLength = j+1-i;
    			Console.WriteLine(endLength);
    			longPal.Append(s.Substring(i, endLength));
    		}
    		i--;
    		j++;
    	}
    }
    }
    

    Python

    class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        self.longPal = ""
        if len(s)<2:
            return s
        for i in range(len(s)):
            self.longPalHelper(s, i, i)
            self.longPalHelper(s, i, i+1)
        return self.longPal
            
    def longPalHelper(self, s, i, j):
        while(i>=0 and j<len(s) and s[i] == s[j]):
            if(j-i+1 > len(self.longPal)):
                endLen = j+1-i
                print endLen
                self.longPal=""
                self.longPal=s[i:endLen+i]
            i-=1
            j+=1

  • 0
    M

    Same here. This is insane. I am suppose to prep up for interviews, not spend hours optimizing constant in the algo.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.