Word transformation

Given a starting word s, an ending word t and a dictionary d. Determine if its possible to go from s to t using the words in the dictionary.

Solution

• Do a BFS on the hypothetical graph from starting word outwards
• From each word, iterate through the letters in the word one at a time and compute a list of all possible 1 char transformations from that word.
• Repeat this until we reach t or run out of nodes to examine

Code

def is_word_transformable(s, t, d)
    q = [s: 0]
    while !q.empty?
        e, count = q.pop
        if e == t
            return true
        end
        one_char_transformation(e).do |word|
            q.insert(word, count+1)
        end
    end

    return false
end

def one_char_transformation(word)
    result = []
    for i in 0..word.size do
        for j in 0..26 do
            if is_valid(d, word[i] = 'a' + j)
                result << word
            end
        end
    end

    result
end

Complexity

• Time complexity: total number of words in the dictionary is d, and max number of edges is d^2
• BFS complexity is O(E+V) = O(d+d^2) = O(d^2)
• Space: O(d)