如何高效地测试字符串是否仅有一个差异？

Question

如何高效地测试字符串是否仅有一个差异？

javastring

3

我在技术面试中被问到这个问题。问题是：给定一个目标和一个字符串数组，返回一个包含所有与目标只有一个不同之处的字符串的数组。

例如，如果目标是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

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

谢谢。

- bZhang

6

实现 https://en.wikipedia.org/wiki/Levenshtein_distance 应该就足够了。 - zubergu

ccat怎么样？它应该有一个差异为1吗？ - Roel Strolenberg

@zubergu，LD通常是O（n*m），已经被优化为O（max（n，m））的时间复杂度。线性扫描则是O（min（n，m））。 - Aaron W.

为什么这被标记为Java？它应该是语言无关的。 - azurefrog

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jsurf · Accepted Answer

如zubergu所提到的，Levenshtein距离将解决您的问题。您可以在Java中找到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，则是可以接受的。