Convert string a to b using word dictionary

Question

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

How can I 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" 

decision:

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

EDIT: The solutions below suggest constructing a graph from dictionary words, so that each word will have an edge for all other words that differ by only one character. This can be a little tricky if the dictionary is too large (let's say we are not only talking about words in English).

Also, even if this is acceptable, what is the best algorithm for creating such a chart? Searching for edges from a word to all other words will be O (n), where n is the size of the dictionary. And the construction of a full schedule would be O (n2)? Any better algorithm?

This is not a domestic problem, but an interview question.

Answer 1

You can think of it as a graph search problem. Each word is a node on the graph, and there is an edge between two words if they differ in exactly one letter. Running BFS over this graph will find the shortest path between your start word and the target word (if you can turn one word into another) and let you know that you won’t do it otherwise.

Answer 2

Just make a BFS according to the schedule, the nodes of which are words, and there is an edge between two nodes if the words on the nodes differ in one letter. Thus, you can provide a solution by running BFS from a given start word. If you reach the destination node, then this is possible, otherwise not.

You can also indicate the steps taken and note that you will provide the fewest steps to get the required bonus.

PS: It is a coincidence that this question was also asked in an interview, and I encoded this solution!

Answer 3

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

This is the line O(nm)

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

The algorithm is simple, if the word from the dictionary does not correspond to the entered 1-character, consider it as 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 

Answer 4

Pre-build and reuse travel maps. For example, build scity [] [] with a valid word distance that can be reused.

Just a quick job search exercise can 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); }