First what you want is not the Hamming distance but the Levenshtein distance (the Hamming distance in fact assumes that the two strings (in this case lists) have the same size).
Computing the Levenshtein distance is not trivial and to build an efficient algorithm you need to use the dynamic programming (otherwise you can come up with a recursive algorithm that is less efficient).
The approach is the following:
A list can be transformed in a second one by applying tree different operations to an element: insert, remove, modify.
With this in mind we design the algorithm as follow:
we keep a matrix M where
M[i][j] = distance between the first i-th elms of the the first list and the first j-th elems of the second list.
Thus, the first row of the matrix represents the distance between an empty list and the second list if you consider only the first i-th elements. Thus it has to initialized as follow:
for i in range(len(l1)):
M[i] = i
because we can always transform a list to the empty one by dropping all the elements (so i operations).
Similarly first column also is initialized in the same way:
for i in range(len(l2)):
M[i] = i
At this point to compute the distance between the first i elements of l1 and the first j elements of l2 we have to consider which is the operation that will transform l1 to l2 with fewer operations. So we take the minimum between
- the number of operations to transform l1[0:i-1] into l2[0:j] + 1 (the added 1 is the cost for this operation which is the deletion)
- the number of operations that we had to perform to transform l1[0:i] into l2[0:j-1] + 1 (this represent the insertion operation)
- and the number of operations to transform l1[0:i-1] into l2[0:j-1]. Summing 1 if l1[i] != l2[j] (we have to substitute te element), 0 otherwise.
This translated into formula is:
M[i][j] = min(M[i-1][j] + 1, M[i][j-1] + 1, M[i-1][j-1] + 1 if l1[i]==l2[j] else 0
Implementing everything in java is:
public static int editDistance(List<String> l1, List<String> l2)
int M = new int[l1.size()][l2.size()];
for(int i = 0; i < l2.size();i++)
M[i] = i;
for(int i = 0; i < l1.size(); i++)
M[i] = i;
for(int i = 1; i < l1.size(); i++)
for(int j = 1; j < l2.size(); j++)
int substitute = 0;
substitute = 1;
int minRemoveAdd = Math.min(M[i - 1][j] + 1, M[i][j - 1] + 1);
M[i][j] = Math.min(minRemoveAdd, M[i-1][j-1] + substitute);
return M[l1.size() - 1][l2.size() - 1];