public int minDistance(String word1, String word2) {
		int length1 = word1.length();
		int length2 = word2.length();

		if (length1 == 0) {
			return length2;
		}

		if (length2 == 0) {
			return length1;
		}
		
		// dp[i][j] is the edit distance between two strings with length i and
		// length j
		int[][] dp = new int[length1 + 1][length2 + 1];
		for (int i = 0; i <= length1; i++) {
			dp[i][0] = i;
		}
		for (int j = 0; j <= length2; j++) {
			dp[0][j] = j;
		}
		
		for (int i = 0; i < length1; i++) {
			char c1 = word1.charAt(i);
			for (int j = 0; j < length2; j++) {
				char c2 = word2.charAt(j);
				if (c1==c2){
					dp[i+1][j+1] = dp[i][j];
				}
				else{
					int insert = dp[i][j+1] + 1;
					int delete = dp[i+1][j] + 1;
					int replace = dp[i][j] + 1;
					int minDistance = insert < delete ? insert : delete;
					minDistance = minDistance < replace ? minDistance : replace;
					dp[i+1][j+1] = minDistance;
				}
			}
		}
		return dp[length1][length2];
	}