Click here to see the full article post
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?
- Sort the 2 words
- 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.