Algorithmus zur Transformation ein Wort zum anderen durch gültige Worte

Question

ich auf diese Variation von edit-distance Problem kam:

Entwurf ein Algorithmus, der eine Quellenwort zu einem Zielwort umwandelt. Zum Beispiel: Von Kopf bis Fuß, in jedem Schritt können Sie nur ein Zeichen ersetzen, und das Wort muss gültig sein. Sie erhalten ein Wörterbuch.

Es ist eindeutig eine Variante des edit distance Problems, aber in Bearbeitungsabstand ist mir egal, ob das Wort gültig ist oder nicht. Wie kann ich diese Anforderung hinzufügen, um die Entfernung zu bearbeiten?

Answer 1

Dies kann als Grafikproblem modelliert werden. Sie können sich die Wörter als Knoten des Graphen vorstellen, und zwei Knoten sind genau dann miteinander verbunden, wenn sie dieselbe Länge haben und sich in einem Zeichen unterscheiden.

Sie können das Wörterbuch vorverarbeiten und diese Grafik erstellen, sollte wie folgt aussehen:

stack jack 
    |  | 
    |  | 
    smack back -- pack -- pick 

Sie können das Wort dann darstellt, eine Zuordnung von dem Wort zu dem Knoten dies für Sie eine Hash-Tabelle verwenden können, Höhe ausgeglichen BST ...

Sobald Sie die oben Mapping an der richtigen Stelle, alles, was Sie dort sehen zu tun haben, wenn Sie einen Pfad zwischen den beiden Graphen Knoten besteht, die leicht durchgeführt werden kann BFS oder DFS verwenden.

So kann man den Algorithmus so zusammenfassen:

preprocess the dictionary and create the graph. 
Given the two inputs words w1 and w2 
if length(w1) != length(w2) 
Not possible to convert 
else 
n1 = get_node(w1) 
n2 = get_node(w2) 

if(path_exists(n1,n2)) 
    Possible and nodes in the path represent intermediary words 
else 
    Not possible 

Answer 2

Ich glaube nicht, dass dies Bearbeitungsabstand ist.

Ich denke, das kann mit einem Graphen gemacht werden. Konstruieren Sie einfach einen Graphen aus Ihrem Wörterbuch und versuchen Sie, mit Ihrem bevorzugten Graph-Traversal-Algorithmus zum Ziel zu navigieren.

Answer 3

codaddict des Graphen Ansatz ist gültig, wenn es O (n^2) Zeit in Anspruch nimmt jedes Diagramm zu bauen, wobei n die Anzahl der Wörter eines bestimmten ist Länge. Wenn das ein Problem ist, können Sie viel effizienter eine bk-tree erstellen, die es ermöglicht, alle Wörter mit einer bestimmten Bearbeitungsdistanz (in diesem Fall 1) eines Zielworts zu finden.

Answer 4

Dies ist eindeutig ein Permutationsproblem. Die Verwendung eines Graphen ist übertrieben. Der Problemstatement fehlt eine wichtige Einschränkung; , dass Sie jede Position nur einmal ändern können. Dies macht dann implizit, dass die Lösung innerhalb von 4 Schritten erfolgt. Alles, was jetzt entschieden werden muss, ist die Reihenfolge der Ersetzen-Operationen:

Operation1 = Wechsel „H“ nach „T“
Operation2 = Wechsel „E“ auf „A“
operation3 = Wechsel „A“ „I“
Operation4 = Wechsel „D zu‚L‘

die Lösung, die Sequenz von Operationen ist eine Permutation der Zeichenfolge‚1234‘, wobei jede Ziffer die Position des Zeichens darstellt, ersetzt. zB "3124" zeigt an, dass zuerst Operation3, dann Operation1, dann Operation2 und dann Operation4 angewendet werden. Bei jedem Schritt, wenn das sich ergebende Wort nicht im Wörterbuch ist, überspringe die nächste Permutation.Ziemlich trivial Ode jemand?

Answer 5

Erstellen Sie ein Diagramm mit jedem Knoten, der das Wort im Wörterbuch darstellt. Fügen Sie eine Kante zwischen zwei Wortknoten hinzu, wenn sich ihre entsprechenden Wörter im Bearbeitungsabstand von 1 befinden.Dann würde die minimale Anzahl von erforderlichen Transformationen die Länge des kürzesten Pfades zwischen dem Quellknoten und dem Zielknoten sein.

Answer 6

Dies ist C# -Code, um das Problem mit BFS zu lösen:

//use a hash set for a fast check if a word is already in the dictionary 
    static HashSet<string> Dictionary = new HashSet<string>(); 
    //dictionary used to find the parent in every node in the graph and to avoid traversing an already traversed node 
    static Dictionary<string, string> parents = new Dictionary<string, string>(); 

    public static List<string> FindPath(List<string> input, string start, string end) 
    { 
     char[] allcharacters = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}; 

     foreach (string s in input) 
      Dictionary.Add(s); 
     List<string> currentFrontier = new List<string>(); 
     List<string> nextFrontier = new List<string>(); 
     currentFrontier.Add(start); 
     while (currentFrontier.Count > 0) 
     { 
      foreach (string s in currentFrontier) 
      { 
       for (int i = 0; i < s.Length; i++) 
       { 
        foreach (char c in allcharacters) 
        { 
         StringBuilder newWordBuilder = new StringBuilder(s); 
         newWordBuilder[i] = c; 
         string newWord = newWordBuilder.ToString(); 
         if (Dictionary.Contains(newWord)) 
         { 
          //avoid traversing a previously traversed node 
          if (!parents.Keys.Contains(newWord)) 
          { 
           parents.Add(newWord.ToString(), s); 
           nextFrontier.Add(newWord); 
          } 

         } 
         if (newWord.ToString() == end) 
         { 
          return ExtractPath(start, end); 

         } 
        } 
       } 
      } 
      currentFrontier.Clear(); 
      currentFrontier.Concat(nextFrontier); 
      nextFrontier.Clear(); 
     } 
     throw new ArgumentException("The given dictionary cannot be used to get a path from start to end"); 
    } 

    private static List<string> ExtractPath(string start,string end) 
    { 
     List<string> path = new List<string>(); 
     string current = end; 
     path.Add(end); 
     while (current != start) 
     { 
      current = parents[current]; 
      path.Add(current); 
     } 
     path.Reverse(); 
     return path; 
    } 

Answer 7

Sie einfach rekursiv Back-Tracking verwenden könnte, aber das ist bei weitem nicht der optimalste Lösung.

# Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only 
# one letter at a time. The new word you get in each step must be in the 
# dictionary. 

# def transform(english_words, start, end): 

# transform(english_words, 'damp', 'like') 
# ['damp', 'lamp', 'limp', 'lime', 'like'] 
# ['damp', 'camp', 'came', 'lame', 'lime', 'like'] 


def is_diff_one(str1, str2): 
    if len(str1) != len(str2): 
     return False 

    count = 0 
    for i in range(0, len(str1)): 
     if str1[i] != str2[i]: 
      count = count + 1 

    if count == 1: 
     return True 

    return False 


potential_ans = [] 


def transform(english_words, start, end, count): 
    global potential_ans 
    if count == 0: 
     count = count + 1 
     potential_ans = [start] 

    if start == end: 
     print potential_ans 
     return potential_ans 

    for w in english_words: 
     if is_diff_one(w, start) and w not in potential_ans: 
      potential_ans.append(w) 
      transform(english_words, w, end, count) 
      potential_ans[:-1] 

    return None 


english_words = set(['damp', 'camp', 'came', 'lame', 'lime', 'like']) 
transform(english_words, 'damp', 'lame', 0) 

Answer 8

Ich glaube nicht, wir brauchen Graph oder eine andere komplizierte Datenstruktur. Meine Idee ist, das Wörterbuch als HashSet zu laden und Methode zu verwenden, um herauszufinden, ob das Wort im Wörterbuch existiert oder nicht.

Bitte überprüfen Sie diese Pseudo-Code meine Idee, um zu sehen:

Two words are given: START and STOP. 
//List is our "way" from words START to STOP, so, we add the original word to it first. 
    list.add(START); 
//Finish to change the word when START equals STOP. 
    while(!START.equals(STOP)) 
//Change each letter at START to the letter to STOP one by one and check if such word exists. 
    for (int i = 0, i<STOP.length, i++){ 
     char temp = START[i]; 
     START[i] = STOP[i]; 
//If the word exists add a new word to the list of results. 
//And change another letter in the new word with the next pass of the loop. 
     if dictionary.contains(START) 
      list.add(START) 
//If the word doesn't exist, leave it like it was and try to change another letter with the next pass of the loop. 
     else START[i] = temp;} 
    return list; 

Wie ich meinen Code verstehen sollte, wie das funktioniert:

Eingang: DAMP, LIKE

Ausgang: DAMP, LAMPE, LIMP, LIME, WIE

Eingang: BACK,

Ausgang PICK: BACK, PACK, PICK