CODEWITHSUNDEEP
algorithmdata-structuresgraph
user2250246
user2250246

Reputation: 3967

Convert string a to b using a dictionary of words

You have a dictionary of words and two strings a and b.

How can one convert a to b by changing only one character at a time and making sure that all the intermediate words are in the dictionary?

Example:

dictionary: {"cat", "bat", "hat", "bad", "had"}
a = "bat"
b = "had"

solution:

"bat" -> "bad" -> "had"

EDIT: The solutions given below propose building a graph from the dictionary words such that every word will have an edge to all other words differing by just one character. This may be somewhat difficult if the dictionary is too big (let us say we are not talking about english language words only).

Also, even if this is acceptable, what is the best algorithm to create such a graph? Finding edges from a word to all other words would be O(n) where n is dictionary size. And total graph construction would be O(n2)? Any better algorithm?

This is not homework problem but an interview question.

Upvotes: 4

Views: 2161

Answers (4)

Jeff Ding
Jeff Ding

Reputation: 1

Pre-build and re-use a travel map. For example, build a scity[][] with valid word distance, that can be re-used.

Just a quick-exercise for job hunting, might be simplified.

#define SLEN 10
char* dict[SLEN]={
"bat",
"hat",
"bad",
"had",
"mad",
"tad",
"het",
"hep",
"hady",
"bap"};

int minD=0xfffff;
int edst(char *a, char *b)
{
 char *ip=a,*op=b;
 int d=0;
 while((*ip)&&(*op))
  if(*ip++!=*op++) 
  {
   if(d) return 0;
   d++;
  }
 if((*op)||(*ip)) d++;
 return d;
}
int strlen(char *a)
{
 char *ip=a;
 int i=0;
 while(*ip++)
  i++;
 return i;
}
int valid(char *dict[], int a, int b)
{
 if((a==b)||(strlen(dict[a])!=strlen(dict[b]))||(edst(dict[a],dict[b])!=1)) return 0;
 return 1;
}

void sroute(int scity[SLEN][SLEN], char* dict[], int a[], int end, int pos)
{
 int i,j,d=0;
 if(a[pos]==end)
 {
  for(i=pos;i<(SLEN-1);i++)
  {
   printf("%s ",dict[a[i]]);
   d+=scity[a[i]][a[i+1]];
  }
  printf(" %s=%d\n",dict[a[SLEN-1]],d);
  if(d<minD) minD=d;
  return;
 }

 for(i=pos-2;i>=0;i--)
 {
  int b[SLEN];
  for(j=0;j<SLEN;j++) b[j]=a[j];
  b[pos-1]=a[i];
  b[i]=a[pos-1];
  if(scity[b[pos-1]][b[pos]]==1)
    sroute(scity,dict,b,end,pos-1);
 }
 if(scity[a[pos-1]][a[pos]]==1) sroute(scity,dict,a,end,pos-1);
}

void initS(int scity[SLEN][SLEN], char* dict[], int a, int b)
{
 int i,j;
 int c[SLEN];
 for(i=0;i<SLEN;i++)
  for(j=0;j<SLEN;j++)
   scity[i][j]=valid(dict,i,j);
 for(i=0;i<SLEN;i++) c[i]=i;
 c[SLEN-1]=b;
 c[b]=SLEN-1;

 sroute(scity, dict, c, a, SLEN-1);
 printf("min=%d\n",minD);
}

Upvotes: 0

Khaled.K
Khaled.K

Reputation: 5940

How can one convert a to b by changing only one character at a time and making sure that all the intermediate words are in the dictionary?

This is straight O(nm)

where n is number of words in the dictionary and m is number of characters in the input word

The algorithm is simple, if the word from the dictionary mismatch the input by 1-character, consider it a solution:

FOR EACH WORD W IN DICTIONARY DO

    IF SIZE(W) = SIZE(INPUT) THEN

        MIS = 0

        FOR i: 1..SIZE(INPUT) IF W[i] != INPUT[i] THEN MIS = MIS + 1

        IF MIS = 1 THEN SOLUTION.ADD(W)

    END-IF

END-FOR

Upvotes: 0

Sankalp
Sankalp

Reputation: 2824

Simply do a BFS over the graph whose nodes are the words and there is an edge between two nodes iff the words on the nodes differ by one letter. In this way, you could provide a solution by starting BFS from the start word given. If you reach the destination node, then it's possible, otherwise not.

You could also provide the steps taken and note that you would be providing the least number of steps to derive the required as a bonus.

P.S.: It's a coincidence that this question was asked to me too in an interview and I coded this solution!

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372814

You can think of this as a graph search problem. Each word is a node in the graph, and there is an edge between two words if they differ by exactly one letter. Running a BFS over this graph will then find the shortest path between your start word and the destination word (if it's possible to turn one word into the other) and will report that there is no way to do this otherwise.

Upvotes: 2

Related Questions