Same code, Java accepted, python TLE


  • 0
    R

    Python code TLE for case "a".

    class Solution:
        def palindrome(self, s, left, right):
            for i in xrange((right - left) / 2):
                if s[left + i] != s[right - 1 - i]:
                    return False
            return True
        # @param s, a string
        # @return a list of lists of string
        def minCut(self, s):
            if len(s) == 1:
                return 0
            
            pali = [99999 for i in xrange(len(s) + 1)]
            pali[0] = -1
            
            for i in xrange(1, len(s) + 1):
                for j in xrange(i - 1, -1, -1):
                    if pali[j] + 1 < pali[i] and self.palindrome(s, j, i):
                        pali[i] = pali[j] + 1
            return pali[-1]
    

    Even I put a

    if len(s) == 1:
                return 0
    

    there.

    And translated Java code is accepted.

    public class Solution {
        boolean palindrome(String s, int left, int right)
        {
            int l = (right - left) / 2;
            for(int i = 0; i < l; i++){
                if (s.charAt(left + i) != s.charAt(right - 1 - i))
                    return false;
            }
            return true;
        }
        public int minCut(String s) {
            int len = s.length();
            Integer[] pali = new Integer[len + 1];
            Arrays.fill(pali, 99999);
            pali[0] = -1;
            
            for(int i = 1; i < len + 1; i++)
            {
                for(int j = i - 1; j > -1 ; j--)
                {
                    if (pali[j] + 1 < pali[i] && palindrome(s, j, i)){
                        pali[i] = pali[j] + 1;
                    }
                }
            }
            return pali[len];
        }
    }

  • 0
    G

    From my experience, it happens now and then that the same algorithm gets accepted in one language but TLE in another. In many cases, this means the algorithm itself is not sufficiently optimized though, which can be told from the runtime distribution.


  • 0
    L
    This post is deleted!

Log in to reply
 

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