CODEWITHSUNDEEP
javastringalgorithm
aviad
aviad

Reputation: 8278

How to transform one string to another with minimal number of edits?

I was asked this question during phone interview.

Given two strings find the minimal number of edits required in order to transform one string to another. The solution needs to be implemented in java and run in O(n*m), assuming that n and m are the lengths of the input strings.

Example:
strings: milk -> beer
min edits: 4

Upvotes: 3

Views: 1776

Answers (2)

Sandeep
Sandeep

Reputation: 7334

Assumption:Word contains distinct letters.

How about creating Character Hashset for S1.

Now iterate through each character in S2 and try to remove it from Hashset of S1. If you can remove the character, dont increment the counter. else increment the counter.

The counter contains the minimum number of edits.

Upvotes: 0

Ryan Amos
Ryan Amos

Reputation: 5452

For strings of the different length, use the Levenshtein Distance: http://en.wikipedia.org/wiki/Levenshtein_distance

If you have strings of equal length and you do not want to consider insertions or deletions, the Hamming Distance is more efficient: http://en.wikipedia.org/wiki/Hamming_distance

Example implementations of Levenshtein distance: http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance

Upvotes: 6

Related Questions