Wie die Berechnung "kürzeste Entfernung" zwischen zwei Wörtern?

Kürzlich hatte ich ein interview und ich wurde gebeten zu schreiben, einen Algorithmus zu finden, die minimale Anzahl von 1 Brief verpasst zu bekommen von einem bestimmten Wort zu einem bestimmten Wort , D. H. Cat->Wiege->Zahn->Hund

Ich will nicht die Lösung des Problems einfach mich durch, Wie kann ich die Verwendung von BFS in diesem Algorithmus ?

  • Ich glaube, Sie suchen nach einem besseren Algorithmus als das BFS.
  • Ein standard-BFS Umsetzung wird gut. Nur im Kopf behalten für ein BFS: "[Priorität] - Warteschlange" .. ansonsten, was haben Sie versucht? (Siehe die standard wikipedia-Artikel für übersichten .. die erklären, eine BFS-Implementierung eher einfach.)
  • Sind Sie sicher, dass keine anderen Anforderungen? Ansonsten können Sie nur Scannen Sie das Wort, spiegeln Figuren wie erforderlich.
  • Das ist verwirrend ? Sind die beiden Wörter die gleiche Länge ? Was ist falsch mit akappa Lösung ?
  • Tun, die zwischen "Worten" werden müssen, um die tatsächlichen Wörter aus einem Wörterbuch gegeben? Oder wäre "Cat->Dat->Dag->Hund" akzeptabel, auch wenn "Dat" ist nicht ein Wort?
  • duplizieren stackoverflow.com/questions/1521958/...

InformationsquelleAutor Dude | 2012-08-04
  1. 5

    gemäß dieser scrabble-Liste, der kürzeste Weg zwischen Katze und Hund ist:
    ['CAT', 'COT', 'KOGGE', 'HUND']

    from urllib import urlopen

def get_words():
    try:
        html = open('three_letter_words.txt').read()
    except IOError:
        html = urlopen('http://www.yak.net/kablooey/scrabble/3letterwords.html').read()
        with open('three_letter_words.txt', 'w') as f:
            f.write(html)

    b = html.find('<PRE>') #ignore the html before the <pre>
    while True:
        a = html.find("<B>", b) + 3
        b = html.find("</B>", a)
        word = html[a: b]
        if word == "ZZZ":
            break
        assert(len(word) == 3)
        yield word

words = list(get_words())

def get_template(word):
    c1, c2, c3 = word[0], word[1], word[2]
    t1 = 1, c1, c2
    t2 = 2, c1, c3
    t3 = 3, c2, c3
    return t1, t2, t3

d = {}
for word in words:
    template = get_template(word)
    for ti in template:
        d[ti] = d.get(ti, []) + [word] #add the word to the set of words with that template

for ti in get_template('COG'):
    print d[ti]
#['COB', 'COD', 'COG', 'COL', 'CON', 'COO', 'COO', 'COP', 'COR', 'COS', 'COT', 'COW', 'COX', 'COY', 'COZ']
#['CIG', 'COG']
# ['BOG', 'COG', 'DOG', 'FOG', 'HOG', 'JOG', 'LOG', 'MOG', 'NOG', 'TOG', 'WOG']

import networkx
G = networkx.Graph()

for word_list in d.values():
    for word1 in word_list:
        for word2 in word_list:
            if word1 != word2:
                G.add_edge(word1, word2)

print G['COG']
#{'COP': {}, 'COS': {}, 'COR': {}, 'CIG': {}, 'COT': {}, 'COW': {}, 'COY': {}, 'COX': {}, 'COZ': {}, 'DOG': {}, 'CON': {}, 'COB': {}, 'COD': {}, 'COL': {}, 'COO': {}, 'LOG': {}, 'TOG': {}, 'JOG': {}, 'BOG': {}, 'HOG': {}, 'FOG': {}, 'WOG': {}, 'NOG': {}, 'MOG': {}}

print networkx.shortest_path(G, 'CAT', 'DOG')
['CAT', 'OCA', 'DOC', 'DOG']

    Als bonus bekommen wir die am weitesten:

    print max(networkx.all_pairs_shortest_path(G, 'CAT')['CAT'].values(), key=len)
#['CAT', 'CAP', 'YAP', 'YUP', 'YUK']
    • Dank Dude!!! Ich hatte für die Installation von python zu laufen, aber es war es Wert .. genial algo 😀
    • Die Hausaufgaben-tag bedeutet, dass Sie sollten geben die Richtlinien und die NICHT vollständige Antworten, wie geschrieben steht in der tag-Beschreibung: This lets potential answerers know that they SHOULD guide the student in solving the problem, and SHOULD NOT simply show the complete answer. Bitte vermeiden Sie dies in Zukunft
    • Hat CAT->OCA oder OCA->DOC bilden einen einzigen Buchstaben ändern? Ich war unter der Annahme, dass dies war ein "Wort ladder" und es war kein vertauschen der Reihenfolge, d.h. Hamming-Distanz und so.
    • Maple, du hast Recht. für die KATZE, t1 = c1, c2 = C, a. OCA, t3 = c2, c3 = C, A. t1 = t3, so dass es zu Ihnen passt. Wenn Sie vermeiden möchten, t1 passenden t3, fügen Sie einen index für jede Vorlage: t1 = 1, c1, c2 t2 = 2, c1, c3 t3 = 3, c2, c3
    • wir erhalten dann ['CAT', 'COT', 'KOGGE', 'HUND']
    InformationsquelleAutor robert king
  2. 4

    Auf den ersten Blick habe ich natürlich über Die Levenshtein-Distanz aber Sie verwenden müssen, BFS. Also ich denke, dass Sie beginnen sollten, aus dem Gebäude Struktur. Wort sollte root sein und dann nächsten Knoten sind Worte, die ersten Buchstaben geändert. Next Knoten geändert haben, zweiter Brief. Beim erstellen der Grafik, die Sie verwenden, BFS und wenn finden Sie neue word-speichern-Pfad Länge. Am Ende des Algorithmus wählen Sie die minimale Distanz.

    InformationsquelleAutor janisz
  3. 0

    1. Beginnen, nur mit dem starten von word in Ihrem Pfad gesetzt werden.

    2. Wenn der Schluss-Wort von jedem Pfad in Ihrem Pfad gesetzt werden, ist das gewünschte Wort, aufhören, dass Pfad den gewünschten Pfad.

    3. Ersetzen Sie jeden Pfad in die path-set mit allen möglichen Pfad, beginnt mit diesem Weg, aber ein Wort mehr.

    4. Gehen Sie zu Schritt 2.

    InformationsquelleAutor David Schwartz
  4. 0

    Wenn wir anfangen zu bauen einen gerichteten azyklischen Graphen aus der Ziel-Wort, um die Quelle zu Wort, die in einem Breite-Weise Mode, und wir machen ein Wörterbuch look-up um zu überprüfen, ob wir gesehen haben, das Wort oben in dem Baum, während Sie durch das Wort, dann das erste vorkommen des Quell-Wort geben sollten, den kürzesten Weg in der umgekehrten Richtung, aus dem 'target-Wort' der 'Ausgangswort'.

    Daraus können wir drucken, den Weg von der 'Quelle' zum 'Ziel'

    InformationsquelleAutor Arvind
Schreibe einen Kommentar