   # Given list of word in dictionary, how to find minimum of steps to change a given word to another?

58 views

Given {cap, cat, mat, map}
Input: cap, mat

Number of Steps: 2 posted Oct 15, 2015

You can model it as a graph problem where words will be nodes of the graph and two
nodes are connected if and only if they are of same length and differ in one char.

You can preprocess the dictionary and create this graph, an example of such processing is -

fix cap stack
| | |
six cat smack
|
mat
|
map

Then you can have a mapping from the word to the nodes of graph representing the word, which can be done using map (or HashMap in Java).

Once you have the above mapping in place, all you have to do is see if there exists a path between the two graph nodes, which can easily be done using BFS and you can also calculate the min distance also using BFS. answer Oct 19, 2015
Similar Questions
+1 vote

Given a string and dictionary of words, form a word by removing minimum number of characters.
Characters can be removed in-order only.

Given a dictionary of strings and another string find out if the string is an exact match to some words in the dictionary or varies at most in only one place of some word of the dictionary?

Given an infinite supply of coins of denominations {20,10,5,1}, find out total number of way to make change of given amount - 'n'?
For example, if given amount is 20, there are 10 ways to make this change as shown below -
(1 of 20),(1 of 10 + 2 of 5),(1 of 10 + 1 of 5 + 5 of 1),(1 of 10 + 10 of 1), (2 of 10), (1 of 5 + 15 of 1),(2 of 5 + 10 of 1),(3 of 5 + 5 of 1),(4 of 5),(20 of 1)

If the amount given is 0 then the total number of ways to make change is 1 - using 0 coins of every given denomination.

A binary tree is given and two nodes of this tree is given, we have to find out the algorithm/code for lowest common ancestor of the two given nodes. Common ancestor are the nodes which can be reached from two nodes by following the parent links. Lowest common ancestor is the common ancestor which has the highest depth.

+1 vote

Given an array of denominations and array Count , find minimum number of coins required to form sum S.

for example:

``````  coins[]={1,2,3};
count[]={1,1,3};
``````

i.e we have 1 coin of Rs 1 , 1 coin of Rs 2 , 3 coins of Rs 3.

Now if we input S = 6 then output should be 2 with possible combination : 3+3 = 6