fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. // A Naive recursive Java program to find minimum number 
  8. // operations to convert str1 to str2 
  9. class Ideone { 
  10. 	static int min(int x, int y, int z) 
  11. 	{ 
  12. 		if (x <= y && x <= z) 
  13. 			return x; 
  14. 		if (y <= x && y <= z) 
  15. 			return y; 
  16. 		else
  17. 			return z; 
  18. 	} 
  19.  
  20. 	static int editDist(String str1, String str2, int m, int n) 
  21. 	{ 
  22. 		// If first string is empty, the only option is to 
  23. 		// insert all characters of second string into first 
  24. 		if (m == 0) 
  25. 			return n; 
  26.  
  27. 		// If second string is empty, the only option is to 
  28. 		// remove all characters of first string 
  29. 		if (n == 0) 
  30. 			return m; 
  31.  
  32. 		// If last characters of two strings are same, nothing 
  33. 		// much to do. Ignore last characters and get count for 
  34. 		// remaining strings. 
  35. 		if (str1.charAt(m - 1) == str2.charAt(n - 1)) 
  36. 			return editDist(str1, str2, m - 1, n - 1); 
  37.  
  38. 		// If last characters are not same, consider all three 
  39. 		// operations on last character of first string, recursively 
  40. 		// compute minimum cost for all three operations and take 
  41. 		// minimum of three values. 
  42. 		return 1 + min(editDist(str1, str2, m, n - 1), // Insert 
  43. 					editDist(str1, str2, m - 1, n), // Remove 
  44. 					editDist(str1, str2, m - 1, n - 1) // Replace 
  45. 					); 
  46. 	} 
  47.  
  48. 	public static void main(String args[]) 
  49. 	{ 
  50. 		String str1 = "horse"; 
  51. 		String str2 = "ros"; 
  52.  
  53. 		System.out.println(editDist(str1, str2, str1.length(), str2.length())); 
  54. 	} 
  55. } 
  56. /*This code is contributed by Rajat Mishra*/
  57.  
Success #stdin #stdout 0.06s 32436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/5kGssu
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!