java - 如何有效地测试字符串是否只包含一个差异？

Question

我在一次技术面试中被问到这个问题。问题是:给定一个目标和一个字符串数组，返回一个数组，其中包含与目标只有一个差异的所有字符串。

例如，如果目标是 cat，catt、caT、caa、ca、at <-- 都只有一个区别。相反，cat、cattt、dog、flower、c <-- 没有区别，不应返回。

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

我的方法是:

  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

但是面试官对上面的内容不满意。有人有任何有效/聪明的想法吗？

谢谢

Answer 1

正如 zubergu Levenshtein 所提到的，距离将解决您的问题。您可以在 java here 中找到 Levenshtein 距离.

编辑:由于您将其标记为 java，您可以运行以下 java 代码:

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]));
    }
}

如果您运行代码，您将看到以下输出:

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

如果 distance 是 0 或 1 那么它是可以接受的。