Delete Operation For Two Strings


  • 0

    Click here to see the full article post


  • 1
    M

    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
    S

    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
    4

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


  • 0
    D

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


  • 0
    A

    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.