Optimizing SPOJ edit distance solution I was doing a standard problem of DP (dynamic programming) on SPOJ  Edit Distance using Python.  

t = raw_input()  

for i in range(int(t)):    
   a,b = raw_input(),raw_input()

   r = len(a)
   c = len(b)
   x = [[0]*(c+1) for j in range(r+1)]

   for j in range(c+1):
       x[0][j] = j

   for j in range(r+1):
       x[j][0] = j

   for j in range(1,r+1):
       for k in range(1,c+1):
           if(b[k-1]!=a[j-1]):
              x[j][k] = min(x[j-1][k-1]+1,x[j-1][k]+1,x[j][k-1]+1)
           else:
              x[j][k] = min(x[j-1][k-1],x[j-1][k]+1,x[j][k-1]+1) 

   print x[r][c]


The solution I have proposed is giving T.L.E (Time Limit Exceeded) even though I am using D.P. Is there any way to optimize it further in terms of time complexity or with respect to any feature of Python 2.7 such as input and output?
I've solved that problem in java and c++ (2nd and 3th places in best solutions category :) so I can compare the local and the remote execution time in order to see - how much faster should be your solution in order to pass.

So, the local execution time of my java solution is 78 ms for the such testcase (10 pairs x 2000 chars), the robot's time is 500 ms, so my PC is ~6.5 times faster. Then the following python DP solution takes 3.6 seconds on my PC so, it would take ~23.5 seconds on the remote PC. So if the remote time limit 15 seconds, the following solution must be minimum ~ 1.56 times faster in order to pass. Ufff.... 

import time

try:
    # just to see the Python 2.5 + psyco speed - 17 times faster than Python 2.7 !!!
    import psyco
    psyco.full()
except:
    pass

def editDistance(s1, s2):
    if s1 == s2: return 0 
    if not len(s1):
       return len(s2)
    if not len(s2):
       return len(s1)
    if len(s1) &gt; len(s2):
        s1, s2 = s2, s1
    r1 = range(len(s2) + 1)
    r2 = [0] * len(r1)
    i = 0
    for c1 in s1:
        r2[0] = i + 1
        j = 0
        for c2 in s2:
            if c1 == c2:
                r2[j+1] = r1[j]
            else:
                a1 = r2[j]
                a2 = r1[j]
                a3 = r1[j+1]
                if a1 &gt; a2:
                    if a2 &gt; a3:
                        r2[j+1] = 1 + a3
                    else:
                        r2[j+1] = 1 + a2
                else:
                    if a1 &gt; a3:
                        r2[j+1] = 1 + a3
                    else:
                        r2[j+1] = 1 + a1
            j += 1
        aux = r1; r1 = r2; r2 = aux
        i += 1
    return r1[-1] 

if __name__ == "__main__": 
    st = time.time()
    t = raw_input()  
    for i in range(int(t)):    
        a, b = raw_input(), raw_input()
        print editDistance(a, b)
    #print "Time (s): ", time.time()-st


What I can say - It's very very hard or may be impossible to pass that puzzle using Python and DP approach (using java or c++ - peace of cake). Wait, wait - ask you - what about that two guys that passed using python? Ok, the answer is easy - they use something different. What's exactly? Something that I've used for java solution I think. That stuff just blows away the competitors....