Delete Operation For Two Strings

  • 0

    Click here to see the full article post

  • 1

    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.

  • 0

    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 ???

  • 0

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

  • 0

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

  • 0

    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).

Log in to reply

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