Can Edit Distance be done using 1d array ?

general
1

Edit distance is a classical dp problem which can be done using 2d array … Can it be done using 1D array ?

1 Like
2

@simararorarox9 Yes it can be done using a 2 X N D array because at each step of the computaion we want the dp values of the previous state and after that we can flush the value so,2 X N array is enough to accomplish the task :slight_smile:

3

Yes I followed the same approach like the Longest Common Substring . ! But here we have to have previous computations from nothing to a particular thing ex- ‘’ to ‘adi’ will need to store as 1,2,3 in 2 d array… can you elaboraate ?