i**********e
发帖数: 1145 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: dongfeiwww (feifei), 信区: JobHunting
标 题: [算法] word ladder problem
发信站: BBS 未名空间站 (Mon Jan 24 23:59:22 2011, 美东)
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]. | i**********e
发帖数: 1145 | | g*********s
发帖数: 1782 | 3 "变化"怎么定义？一次只能改动一个字母？能增/删吗？
如果是一次只能改一个，那bfs够了。
bfs可看作dijkstra的特例，dijkstra又可看成A*的特例。
transformed
【在 i**********e 的大作中提到】
: 我的解法在这里，感觉好像还可以进行优化，欢迎各位讨论讨论。
: http://www.mitbbs.com/article/JobHunting/31777619_0.html
| t****t
发帖数: 6806 | 4 牛顿法求sqrt用的函数是y=x^2-a=0...不是用的sqrt.
要取f''(x)同号的那一侧, 即根的右侧比较好. | g*********s
发帖数: 1782 | 5 为什么根右侧好？怎么证明任意初值最后都能收敛呢？
【在 t****t 的大作中提到】
: 牛顿法求sqrt用的函数是y=x^2-a=0...不是用的sqrt.
: 要取f''(x)同号的那一侧, 即根的右侧比较好.
| t****t
发帖数: 6806 | 6 画个图看看就知道了. 注意我没说任意初值都能收敛, 有条件的. 不过对这个问题, 确
实任意初值都能收敛的, 有快有慢就是了.
【在 g*********s 的大作中提到】
: 为什么根右侧好？怎么证明任意初值最后都能收敛呢？
|
|
