跟Albert Einstein医学院的同学打听个老板# Biology - 生物学
d*w
1 楼
amazon好像出过此题,简单的说,就是一个原始字符串,一个目标串,求最少的变换的
路径,要求每次变化后的词都在一个字典中。
有些人说bfs,还是dijkstra算法?
下面是原题
// http://www.cs.duke.edu/csed/newapt/allwordladder.html
A word ladder is a sequence of words in which each word can be transformed
into the next word by changing one letter. For example, the word ladder
below changes 'lot' to 'log'.
lot dot dog log
This is not the shortest word-ladder between 'lot' and 'log' since the
former can be immediately changed to the latter yielding a word ladder of
length two:
lot log
The first and last words in a word ladder are the anchor rungs of the ladder
. Any other words are interior rungs. For example, there are three interior
rungs in the ladder below between 'smile' and 'evote'.
smile smite smote emote evote
In this problem you'll write a method that has parameters representing
potential interior rungs: an array of strings (these may by nonsense or
English words), and the anchor rungs --- two strings. Your code must
determine the shortest word ladder between the anchor rungs that uses at
least one interior rung, and the number of such ladders. Return an array
containing two ints: the first is the length of the shortest valid word
ladder and the second is the number of shortest ladders. If there are no
valid ladders return [0,0].
路径,要求每次变化后的词都在一个字典中。
有些人说bfs,还是dijkstra算法?
下面是原题
// http://www.cs.duke.edu/csed/newapt/allwordladder.html
A word ladder is a sequence of words in which each word can be transformed
into the next word by changing one letter. For example, the word ladder
below changes 'lot' to 'log'.
lot dot dog log
This is not the shortest word-ladder between 'lot' and 'log' since the
former can be immediately changed to the latter yielding a word ladder of
length two:
lot log
The first and last words in a word ladder are the anchor rungs of the ladder
. Any other words are interior rungs. For example, there are three interior
rungs in the ladder below between 'smile' and 'evote'.
smile smite smote emote evote
In this problem you'll write a method that has parameters representing
potential interior rungs: an array of strings (these may by nonsense or
English words), and the anchor rungs --- two strings. Your code must
determine the shortest word ladder between the anchor rungs that uses at
least one interior rung, and the number of such ladders. Return an array
containing two ints: the first is the length of the shortest valid word
ladder and the second is the number of shortest ladders. If there are no
valid ladders return [0,0].