t******e
发帖数: 1293 | 1 Carefully see the following transition from one word to other-
PAN -> PEN -> MEN -> MET
Here each word is achieved by changing any one character in previous word.
Now you are given with a Source word (PAN here) and a Destination word (MET
here) and need to find out shortest transition chain following above rule
using only meaningful words. Dictionary containing thousands of meaningful
words is provided to you. |
B*****t
发帖数: 335 | |
h**k
发帖数: 3368 | 3 把字典变成图，每个单词看作一个vertice，可以互相转变的两个词之间存在一个edge
。然后问题变成找两点之间的最小路径。 |
t******e
发帖数: 1293 | 4 single source shortest path algorithm？
问题在于怎么构造出这个图来？如何快速算出每两个单词的edit distance?
这个时间复杂度很大
【在 B*****t 的大作中提到】
: 所有的SSSP算法可以行吧。
|
B*****t
发帖数: 335 | 5 you are right.
use DP to calculate distance
【在 t******e 的大作中提到】
: single source shortest path algorithm？
: 问题在于怎么构造出这个图来？如何快速算出每两个单词的edit distance?
: 这个时间复杂度很大
|
