CODEWITHSUNDEEP
calgorithmgraph
devsda
devsda

Reputation: 4222

Transforming one word into another word by changing only one letter at a time

How would I approach this algorithmic problem?

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.

Example:

Input: DAMP, LIKE
Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

Upvotes: 1

Views: 7471

Answers (1)

thiton
thiton

Reputation: 36049

Try thinking this problem in terms of graphs: Consider all words in a dictionary as vertices, and insert an edge between each two vertices that differ by only one letter. The output is a well-known object in the graph, and you probably already know an algorithm to solve the problem.

Spoiler:

The output is a path in the graph, and the question is solved by finding a path. A breadth-first search (BFS) or Dijkstra's algorithm solve the problem elegantly.

Upvotes: 7

Related Questions