Cracking the Coding Interview: Fourth Edition (308 page e-book / PDF)
Delivered instantly as a PDF via email. For Software Engineers & SDETs
  • 150 programming interview questions and answers
  • 5 proven approaches to crack algorithm questions
  • 10 mistakes candidates make, and how to avoid them.
  • How to prepare for technical and behavioral questions without wasting your time!
"The BEST book for acing your interview. It helped me land my Microsoft job, and it was worth every penny!" - Ravi (Accepted at Microsoft, Amazon and Facebook) 30 Day Money Back Guarantee: Don't love the book? We'll give you your money back! More Info

Saturday, April 24, 2010

You are given a dictionary of all valid words. You have the following 3 operations permitted on a word: delete a character, insert a character, replace a character. Now given two words - word1 and word2 - find the minimum number of steps required to convert word1 to word2. (one operation counts as 1 step.)
Posted by at
Labels:

2 comments:

  1. AnonymousFebruary 7, 2011 at 9:24 AM

    We can use suffix tree and find the minimum number of insertions or deletions

    ReplyDelete
  2. YuriMay 29, 2011 at 5:07 PM

    You can use edit-distance algorithm for this. Read page 174 of this pdf.... http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

    ReplyDelete

Subscribe to: Post Comments (Atom)