Edit Distance Problem LeetCode

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

 Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

 NOTE:

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

The Edit Distance is a classical algorithm question that is well explained in Wikipedia, LeetCode, and GeeksForGeeks. A collection of hundreds of interview questions and solutions are available in our blog at Interview Question Solutions

Solution

Source: Java1, Java2

	/*
	Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’.
	Insert
	Remove
	Replace
	All of the above operations are of equal cost.
	Examples:
	Input: str1 = "geek", str2 = "gesek"
	Output: 1
	We can convert str1 into str2 by inserting a 's'.
	Input: str1 = "cat", str2 = "cut"
	Output: 1
	We can convert str1 into str2 by replacing 'a' with 'u'.
	Input: str1 = "sunday", str2 = "saturday"
	Output: 3
	Last three and first characters are same. We basically
	need to convert "un" to "atur". This can be done using
	below three operations.
	Replace 'n' with 'r', insert t, insert a
	Solution:
	*/
	package com.alg.dp;
	import java.util.Map;
	import java.util.HashMap;
	/**
	*
	* @author rbaral
	*/
	public class EditDistance {
	/**
	* this method has exponential time complexity as it performs the same
	* operation multiple times. We can get slightly better performance with
	* memoization.
	*
	* @param x
	* @param y
	* @return
	*/
	public static int getEditDistanceTopDown(String x, String y, Map<String, Integer> distMap) {
	//base case
	if (x.length() == 0) {
	return y.length();
	}
	if (y.length() == 0) {
	return x.length();
	}
	//compare the first character
	if (x.charAt(0) == y.charAt(0)) {
	String key = x.substring(1) + "," + y.substring(1);
	if (!distMap.containsKey(key)) {
	distMap.put(key, getEditDistanceTopDown(x.substring(1), y.substring(1), distMap));
	}
	return distMap.get(key);
	} else {
	String key1 = x.substring(1) + "," + y.substring(1);
	String key2 = x + "," + y.substring(1);
	String key3 = x.substring(1) + "," + y;
	if (!distMap.containsKey(key1)) {
	distMap.put(key1, getEditDistanceTopDown(x.substring(1), y.substring(1), distMap));
	}
	if (!distMap.containsKey(key2)) {
	distMap.put(key2, getEditDistanceTopDown(x, y.substring(1), distMap));
	}
	if (!distMap.containsKey(key3)) {
	distMap.put(key3, getEditDistanceTopDown(x.substring(1), y, distMap));
	}
	return 1 + Math.min(distMap.get(key1),
	Math.min(distMap.get(key2),
	distMap.get(key3)));
	}
	}
	public static int getEditDistanceBottomUp(String x, String y) {
	//lets create an auxiliary array to store the edit distances
	int[][] dist = new int[x.length() + 1][y.length() + 1];
	for (int i = 0; i <= x.length(); i++) {
	for (int j = 0; j <= y.length(); j++) {
	if (i == 0) {
	dist[i][j] = j;
	} else if (j == 0) {
	dist[i][j] = i;
	} else if (x.charAt(i - 1) == y.charAt(j - 1)) {//nothing required to do, just proceed with the shorter string
	dist[i][j] = dist[i - 1][j - 1];
	} else {
	//need to find the minimum among the insert, replace, and remove operations
	dist[i][j] = 1 + Math.min(dist[i][j - 1], Math.min(dist[i - 1][j], dist[i - 1][j - 1]));
	}
	}
	}
	return dist[x.length()][y.length()];
	}
	public static void main(String args[]) {
	String str1 = "ocurrance";//sunday";
	String str2 = "occurrence";//saturday";
	int lengthBottomUp = getEditDistanceBottomUp(str1, str2);
	System.out.println("edit distance bottom up:" + lengthBottomUp);
	Map<String, Integer> distMap = new HashMap<String, Integer>();
	int lengthTopDown = getEditDistanceTopDown(str1, str2, distMap);
	System.out.println("edit distance top down:" + lengthTopDown);
	}
	}

view raw EditDistance.java hosted with ❤ by GitHub