public int minDistance(String word1, String word2) {
		if (word1 == null || word1.length() == 0) {
			return word2.length();
		}
		if (word2 == null || word2.length() == 0) {
			return word1.length();
		}

		int w1 = word1.length();
		int w2 = word2.length();

		int[][] maxCount = new int[w1+1][w2+1];

		int firsti = -1;
		int firstj = -1;
		int endi = -1;
		int endj = -1;
		boolean access = false;
		
		for (int i = 1; i <= w1; i++) {
			for (int j = 1; j <= w2; j++) {
				if (word1.charAt(i-1) == word2.charAt(j-1)) {
					if(!access){
						firsti = i-1;
						firstj = j-1;
						access = true;
					}
					endi = i - 1;
					endj = j - 1;
					
					maxCount[i][j] = maxCount[i - 1][j - 1] + 1;
				} else {
					maxCount[i][j] = Math.max(maxCount[i - 1][j],
							maxCount[i][j - 1]);
				}
			}
		}

		int minDistance = 0;
		if(firsti == -1){
			minDistance = Math.max(w1, w2);
		} else {
			System.out.println("firsti:" + firsti + " endi:" + endi +
					           " firstj:" + firstj + " endj:" + endj); 
			minDistance = Math.max(firsti, firstj) + Math.max(endi - firsti + 1 - maxCount[w1][w2],
					endj - firstj + 1 - maxCount[w1][w2]) + Math.max(w1 - endi - 1,	w2 - endj - 1);
		}

		return minDistance;
	}