top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration

Facebook Login
Site Registration

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

+2 votes
60 views

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

Number of Steps: 2

posted Oct 15, 2015 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

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.

For more infoclick here

answer Oct 19, 2015 by Mohammed Hussain
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.

+4 votes

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?

+2 votes

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.

+7 votes

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

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...