Monday, July 18, 2016

word ladder

int (start, end, words):
    startn, endn = (start, end, words)
    count = (startn, endn)
    return count

// time O(n)
(startn, endn):
    mind = null
    q = new
    q.push({startn, 0})
    while !q.isempty():
        n, d = q.dequeue()
        if n == endn:
            mind = d
            break
        if visited.has(n):
            continue
        visited.add(n)
        for nn in n.neighbors:
            q.enqueue({nn, d +1})
    if mind != null:
        mind +=2
    return mind

node:
    word
    neighbors

// time O(n^2)
(s1, s2, words):
    all = [words, s1, s2]
    for word in all:
        wordnodemap[word] = new node(word)
    start = wordnodemap[s1]
    end = wordnodemap[s2]
    for word in all:
        wordn = wordnodemap[word]
        for other in all:
            if word == other:
                continue
            if areladderwords(word, other):
                othern = wordnodemap[other]
                wordn.neighbors.add(othern)
    return start, end

areladderwords(s1, s2):
    count = 0
    for c1, c2 in s1, s2:
        if c1 != c2:
            count++
            if count > 1:
                break
    return count == 1
[Hat tip to A]

No comments:

Post a Comment