The following code problem is one of the Amazon sample interview questions. I think it is written poorly which may be why I don't understand it. I also can't find any posted solutions with a google search. If anyone can help that would be great. Either just elaborate if you think you understand it, or posting some code is good too.
You are given a dictionary of all valid words. You have the following 3 operations permitted on a word: delete a character, insert a character, and replace a character. Now, given two words, $word1 and $word2, write a script to convert $word1 to $word2 using the minimum number of steps required. (One operation counts as 1 step).
Convert word1 to word2 interview question
Moderator: General Moderators
Re: Convert word1 to word2 interview question
Ever played one of those word games where you have to turn one word into another, like "bear" into "claw", by changing one letter at a time? Except each change has to be a real word?
BEAR -> BEAT -> SEAT -> SLAT* -> SLAW* -> CLAW
(* narrow strip of wood; basically a salad, like coleslaw)
Here you can also add and remove letters.
WHITE -> WHIT* -> WIT -> LIT -> LIE
(* a small amount)
Given two words (bear, claw; white, lie) find the shortest path between the two.
BEAR -> BEAT -> SEAT -> SLAT* -> SLAW* -> CLAW
(* narrow strip of wood; basically a salad, like coleslaw)
Here you can also add and remove letters.
WHITE -> WHIT* -> WIT -> LIT -> LIE
(* a small amount)
Given two words (bear, claw; white, lie) find the shortest path between the two.
Re: Convert word1 to word2 interview question
Seems difficult to impossible to write with just what is provided though. They don't provide the dictionary or the words being converted. I would just be tempted to str_split the words to character arrays, parse through each element one at a time beginning to end, then delete any extra letters at the end. That would mean the words in the middle of the operation wouldn't be real words though. You could remove all of the non-shared characters, then insert the missing ones where needed, but that seems like a stretch.
- John Cartwright
- Site Admin
- Posts: 11470
- Joined: Tue Dec 23, 2003 2:10 am
- Location: Toronto
- Contact:
Re: Convert word1 to word2 interview question
You could use pspell_check to check the word permuations, but thats not very efficient
. This one has me stumped.
Re: Convert word1 to word2 interview question
Just pretend you have a hash/dictionary/lookup array that you can use to check if a word exists. Like
There's a "simple" way to do this, but it's really horrible: you brute-force it.
Start systematically doing stuff.
- Too few letters: add a letter
- Too many letters: remove a letter
- Same number of letters: replace a letter
Remember, each new string has to be a word.
Problem is, you're trying to find the shortest path, not any path at all. Which means you have to run all these possibilities at the same time.
Eventually you'll find LIE. But you have to keep track of the path taken. More complexity.
Code: Select all
if (isset($dictionary[$word])) {
// $word is a word
} else {
// $word is not a word
}Start systematically doing stuff.
- Too few letters: add a letter
- Too many letters: remove a letter
- Same number of letters: replace a letter
Remember, each new string has to be a word.
Problem is, you're trying to find the shortest path, not any path at all. Which means you have to run all these possibilities at the same time.
Code: Select all
WHITE
(remove a letter (5), and replace a letter (5*25))
HITE, WITE, WHTE, WHIE, WHIT, AHITE, BHITE..., YHITE, ZHITE, WAITE, WBITE..., WHATE..., WHIAE..., WHITA
(filter to remove only the words that exist and haven't been tried. according to firefox's spellcheck:)
WHIT, WAITE, WRITE, WHILE, WHINE, WHITS
(and repeat. one line per word)
HIT, WIT, WHT, WHI, AHIT..., WAIT..., WHAT..., WHIA...,
AITE, WITE, WATE, WAIE, WAIT, AAITE...,
RITE...,
HILE...,
HINE...,
HITS...