How to test if strings contain only one difference efficiently?

Question

I was asked this question on a technical interview. Question is: given a target, and an array of strings, return an array that contains all strings with ONLY one difference to the target.

For example if target is cat, catt, caT, caa, ca, at <-- are all only one difference. And conversely, cat, cattt, dog, flower, c <-- are not one difference and should not be returned.

oneDiff(String target, String[] a) ...

My approach was:

  ans = []
  for all element e in the array
      count -> 0
      if absoulte(e's length - target length) > 1 
          continue
      endif
      for all character c in e
         scan through, increment count if difference is found. 
      endfor
      if (count == 1) 
         continue
      else 
         add e to ans
  endfor
  return ans

But the interviewer wasnt happy with what's above. Anyone has any efficient/clever ideas?

Thanks

Answer 1

As mentioned by zubergu Levenshtein distance will solve your problem. You can find Levenshtein distance in java here.

Edit: Since you tagged it as java you can run the following java code:

public class Levenshtein {

    public static int distance(String a, String b) {
        a = a.toLowerCase();
        b = b.toLowerCase();
        // i == 0
        int [] costs = new int [b.length() + 1];
        for (int j = 0; j < costs.length; j++)
            costs[j] = j;
        for (int i = 1; i <= a.length(); i++) {
            // j == 0; nw = lev(i - 1, j)
            costs[0] = i;
            int nw = i - 1;
            for (int j = 1; j <= b.length(); j++) {
                int cj = Math.min(1 + Math.min(costs[j], costs[j - 1]), a.charAt(i - 1) == b.charAt(j - 1) ? nw : nw + 1);
                nw = costs[j];
                costs[j] = cj;
            }
        }
        return costs[b.length()];
    }

    public static void main(String [] args) {
        String comparison = "cat";
        String [] data = { "cattt", "catt", "caT", "caa", "ca", "at" };
        for (int i = 0; i < data.length; i++)
            System.out.println("distance(" + comparison + ", " + data[i] + ") = " + distance(comparison, data[i]));
    }
}

If you run the code you will see the following output:

distance(cat, cattt) = 2
distance(cat, catt) = 1
distance(cat, caT) = 0
distance(cat, caa) = 1
distance(cat, ca) = 1
distance(cat, at) = 1

If the distance is 0 or 1 then its acceptable.