StringOneEditApart

/*
Question: Given two strings, return boolean True/False, if they are only one edit apart.Edit can be insert/delete/update of only one character in the string. Eg: 

-True 
xyz,xz 
xyz, xyk 
xy, xyz 


-False 
xyz, xyz 
xyz,xzy 
x, xyz

NOTE: Can be done using EDIT-DISTANCE Algorithm, but IT WONT BE EFFICIENT since the time complexity will be O(n^2)
ans the space complexity will also be O(n^2) if edit distance algorithm is implemented iteratively.

Source: http://www.careercup.com/question?id=5092486548553728
*/

******************************************* Using Iteration ******************************************************

package StringsOneEditApart;

import java.util.Scanner;

public class UsingIterativeEditDistanceAlgorithm {
public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	try{
		System.out.println("Enter the two strings for comparison");
		String s1 = in.nextLine();
		String s2 = in.nextLine();
		if(iterativeEditDistanceAlgorithm(s1,s2)==1)
			System.out.println("True");
		else
			System.out.println("False");
	}
	finally{
		in.close();
	}
}
private static int iterativeEditDistanceAlgorithm(String s1, String s2) {
	int[][] table = new int[s1.length()+1][s2.length()+1];
	for(int i=0;i<table.length;i++)
		table[i][0]=0;
	for(int i=0;i<table[0].length;i++)
		table[0][i]=0;
	
	int left = 0;
	int top = 0;
	int corner=0;
	for(int i=1;i<table.length;i++){
		for(int j=1;j<table[0].length;j++){
			left = table[i-1][j] + 1;
			top = table[i][j-1] +1;
			corner = table[i-1][j-1] + check(s1.charAt(i-1),s2.charAt(j-1));
			table[i][j] = Math.min(Math.min(left,top), corner);
		}
	}
	return table[table.length-1][table[0].length-1];
}

private static int check(char c1, char c2) {
	if(c1==c2)
		return 0;
	return 1;
}
}
/*
Analysis:
	Time Complexity = O(n^2)
	Space Complexity = O(n^2)
	*/

******************************************* Using Iterative Edit Distance Algorithm *********************************
package StringsOneEditApart;

import java.util.Scanner;

public class UsingIterativeEditDistanceAlgorithm {
public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	try{
		System.out.println("Enter the two strings for comparison");
		String s1 = in.nextLine();
		String s2 = in.nextLine();
		if(iterativeEditDistanceAlgorithm(s1,s2)==1)
			System.out.println("True");
		else
			System.out.println("False");
	}
	finally{
		in.close();
	}
}
private static int iterativeEditDistanceAlgorithm(String s1, String s2) {
	int[][] table = new int[s1.length()+1][s2.length()+1];
	for(int i=0;i<table.length;i++)
		table[i][0]=0;
	for(int i=0;i<table[0].length;i++)
		table[0][i]=0;
	
	int left = 0;
	int top = 0;
	int corner=0;
	for(int i=1;i<table.length;i++){
		for(int j=1;j<table[0].length;j++){
			left = table[i-1][j] + 1;
			top = table[i][j-1] +1;
			corner = table[i-1][j-1] + check(s1.charAt(i-1),s2.charAt(j-1));
			table[i][j] = Math.min(Math.min(left,top), corner);
		}
	}
	return table[table.length-1][table[0].length-1];
}

private static int check(char c1, char c2) {
	if(c1==c2)
		return 0;
	return 1;
}
}
/*
Analysis:
	Time Complexity = O(n^2)
	Space Complexity = O(n^2)
	*/
	
*********************************************** Using Recursive Edit Distance Algorithm ******************************
package StringsOneEditApart;

import java.util.Scanner;

public class UsingRecursiveEditDistanceAlgorithm {
public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	try{
		System.out.println("Enter the two strings");
		String s1 = in.nextLine();
		String s2 = in.nextLine();
		if(editDistanceAlgorithm(s1,s2, s1.length(), s2.length()) == 1)
			System.out.println("True");
		else
			System.out.println("False");
	}
	finally{
		in.close();	
	}
}

private static int editDistanceAlgorithm(String s1, String s2, int m, int n) {
	if(m==0 || n==0)
		return 0;
	if(m==0)
		return n;
	if(n==0)
		return m;
	
	int left = editDistanceAlgorithm(s1, s2, m-1, n) + 1 ;
	int top = editDistanceAlgorithm(s1, s2, m, n-1)+1;
	int corner = editDistanceAlgorithm(s1, s2, m-1, n-1)+check(s1.charAt(m-1),s2.charAt(n-1));
	
	return (Math.min(Math.min(left,top), corner));
}

private static int check(char c1, char c2) {
	if(c1==c2)
		return 0;
	else
		return 1;
}
}
/*
Analysis:
	I. Time Complexity:  O(3^(m+n-1)). This is an EXPONENTIAL time algorithm
	
	The recursion formula is,

	T(m,n) = T(m-1,n-1) + T(m-1,n) + T(m,n-1) + 1
	T(0,n) = n
	T(m,0) = m
	is right.

	You can see, that every T(m,n) splits of into three paths. Due to every node runs in O(1) we only have to 
	count the nodes.

	A shortest path has the length min(m,n), so the (recursion)tree has at least 3min(m,n) nodes. But there are 
	some paths that are longer. 
	
	You get the longest path by alternately reduce the first and the second string.
	This path will have the length m+n-1, so the whole tree has at most 3m+n-1 nodes.

	Let m = min(m,n). The tree contains also at least

	enter image description here

	different paths, one for each possible order of reducing n.

	So Ω(2^(max(m,n))) and Ω(3^(min(m,n))) are lower bounds and O(3^(m+n-1)) is an upper bound.
	
	*
	*I. Space Complexity: The space complexity of the algorithm is also EXPONENTIAL (since multiple
	* recursive calls utilizes many stack frames. If the length of the strings is 10^5, the program might crash)
	*
	*/