bond
BAN USER- 0of 0 votes
AnswersSuppose we want to convert one string S1 to another string S2 using only 3 types of operations:
-Insert(pos,char) (costs 8)
-Delete(pos) (costs 6)
-Replace(pos,char) (costs 8)
Find the sequence of steps to convert S1 to S2 such that the cost to convert S1 to S2 is minimum.
Eg. 'calculate' to 'late' - the possible operations are
Delete(0)
Delete(1)
Delete(2)
Delete(3)
Delete(4)
and the above sequence of operations costs 30.
I used the following code(using levenshtein algorithm) to solve this. But I am not getting correct answer.
- bond in United Statestuples=[] ops=[] s1='' s2='' def levenshtein(a,b): global s1,s2 n, m = len(a), len(b) if n > m: a,b = b,a n,m = m,n s1,s2=a,b current = range(n+1) for i in range(0,len(current)): current[i]=current[i]*8 tuples.append(current) for i in range(1,m+1): previous, current = current, [i*8]+[0]*n for j in range(1,n+1): add, delete = previous[j]+6, current[j-1]+8 change = previous[j-1] if a[j-1] != b[i-1]: change=change+8 current[j] = min(add, delete, change) tuples.append(current) return current[n] print levenshtein('calculate','late') for i in range(len(tuples)): stri='' for j in range(len(tuples[0])): stri+=str(tuples[i][j])+' ' i=len(tuples)-1 j=len(tuples[0])-1 ops=[] while i>0: while j>0: minimum=min([tuples[i-1][j],tuples[i][j-1],tuples[i-1][j-1]]) if minimum==tuples[i-1][j]: i=i-1 if not tuples[i][j]==tuples[i-1][j]: ops.append([1,i]) elif minimum==tuples[i][j-1]: j=j-1 if not tuples[i][j]==tuples[i][j-1]: ops.append([2,i-1,j]) else: ops.append([3,i-1,s1[i-1]]) i=i-1 j=j-1
| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Algorithm - 0of 0 votes
AnswersConvert a binary search tree into doubly linked list in sorted order in place.
- bond in India for hyd| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Trees and Graphs
Hey @notbad,really good implementation ..but one bug if a no. is repeated again like
- bond July 27, 2012123,132,213,231,312,321,321
It should give 15 but its giving 21,dat means its treating last 321 as a separate number. Provide corrected code asap .