Dynamic Programming 12

Given two strings s and t. Return the minimum number of operations required to convert s to t. The possible operations are permitted: 

 1. Insert a character at any position of the string. 

2. Remove any character from the string. 

3. Replace any character from the string with any other character.

Problem link :- click here

Code

import java.util.Scanner;

public class DynamicProgramming_12
{
	//Recursion
	static int noOfOperations(String str1, String str2)
	{
		int n1 = str1.length();
		int n2 = str2.length();
		
		if(n1==0 && n2==0)
			return 0;
		if(n1==0  &&  n2>0)
			return n2;
		if(n1>0  &&  n2==0)
			return n1;
		
		if( str1.charAt(0) == str2.charAt(0) )
			return noOfOperations(str1.substring(1), str2.substring(1));
		else
		{
			//Operations are done for str1
			int insert    = noOfOperations( str1,                         str2.substring(1) );
			int remove = noOfOperations( str1.substring(1), str2                         );
			int replace = noOfOperations( str1.substring(1), str2.substring(1) );
			
			return 1 + Math.min( Math.min(insert, remove), replace );
		}
	}
	
	//DP
	static int noOfOperations1(String str1, String str2)
	{
		int n1 = str1.length();
		int n2 = str2.length();
		
		int[][] mat = new int[n1+1][n2+1];
		
		for(int i=0; i<=n1; i++)
		{
			for(int j=0; j<=n2; j++)
			{
				if(i==0)
					mat[i][j] = j;
				else if(j==0)
					mat[i][j] = i;
				else if(str1.charAt(i-1) ==  str2.charAt(j-1))
					mat[i][j] = mat[i-1][j-1];
				else
					mat[i][j] = 1 + Math.min( Math.min(mat[i][j-1], mat[i-1][j]), mat[i-1][j-1]);
			}
		}
		
//		for(int[] x: mat)
//		{
//			for(int y: x)
//				System.out.print(y + "\t");
//			System.out.println();
//		}
		
		return mat[n1][n2];
	}

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		System.out.print("Enter the first String : ");
		String str1 = s.next();
		
		System.out.print("Enter the second String : ");
		String str2 = s.next();
		
		int ans = noOfOperations1(str1, str2);
		System.out.println("\n\n" + ans);
		
		s.close();
	}

}