Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

168. Edit Distance

MediumDay 49 of 60Dynamic Programming

Given two strings word1 and word2, return the minimum number of operations needed to turn word1 into word2. Each operation is one of: insert a character, delete a character, or replace a character. (This is the Levenshtein distance.)

Example 1
Input: word1 = "horse", word2 = "ros"
Output: 3
Replace h with r ("rorse"), delete the middle r ("rose"), delete e ("ros").
Example 2
Input: word1 = "intention", word2 = "execution"
Output: 5
Constraints
  • 0 <= word1.length, word2.length <= 500
  • Both strings are lowercase English letters
Hints
Frequently asked at: Amazon, Google, Microsoft, Goldman Sachs
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min