Wie testen, ob Zeichenfolgen nur eine Differenz effizient enthalten?

Question

Ich wurde diese Frage in einem technischen Interview gestellt. Frage ist: gegeben ein Ziel, und ein Array von Zeichenfolgen, geben Sie ein Array zurück, das alle Zeichenfolgen mit nur einer Differenz zum Ziel enthält.

Zum Beispiel, wenn Ziel ist Katze, Catt, CaT, caa, ca, um < - sind alle nur ein Unterschied. Und umgekehrt, Katze, Katze, Hund, Blume, c < - sind kein Unterschied und sollten nicht zurückgegeben werden.

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

Mein Ansatz war:

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 

Aber der Interviewer war nicht glücklich mit dem, was oben ist. Hat jemand effiziente/schlaue Ideen?

Dank

Answer 1

Wie zubergu Levenshtein Abstand erwähnt wird Ihr Problem lösen. Sie können Levenshtein Entfernung in Java here finden.

Edit: Da Sie es als java markiert können Sie den folgenden Java-Code ausführen:

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

Wenn Sie den Code ausführen Sie die folgende Ausgabe sehen:

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

Wenn die distance ist 0 oder 1 dann ist es akzeptabel.