# Delete Operation For Two Strings

• hello, I have a question. Why is the space complexity of the last solution (DP solution with 1-D arrays) of O(n)? I am confused because the temp array is being reinitialized in every iteration of the loop.

• will following solution work?

1. Sort the 2 words
2. find the difference of 1 character between sorted strings.

example: if Input: "sea", "eat"... these get sorted as "aes" and "aet" so to make these 2 same, we could remove "s" from 1st string and "t" from 2nd string... so answer is 2 ???

• @seakhar order of the characters are important here. think about "seam" and "meat".

• @seakhar , I think sorting isn't the right approach as order of characters matter in this case

• Most DP solutions can be optimized. Instead of calculating all matrix, we actually only need the area with edit distance <= result. Suppose, you have 2 equal strings with length 1 million. With the described approach, you'll process all 1000000000000 cells, while my A* path-finding approach will just go diagonally straight from corner to corner. The listed DP approaches are always O(n*m); my approach can be as fast as max(n,m).

• @seakhar That approach won't work for ["sea", "ate"].

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