g***j
发帖数: 1275 | 1 这个经典题目
Given two words (start and end), and a dictionary, find the length of
shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
我理解的就是构建一个图，如果两个单词之间只有一个字母不一样，就有路径，然后找
从start到end的最短路径，是这样的么？
但是，这个说起来容易写起来难啊，面试的时候难道还要写一个最短路径的算法么？
另外，这个图如何构建呢？如何快速的判断两个单词只有一个字母不一样呢？
以前以为很容易，动手开始写了才知道好难，至少不像平时面试的那种20行就可以搞定
的题目
请问是我理解错了，还是有别的更加优化的算法？
谢谢了！ |
v****t
发帖数: 338 | 2 显然不是20行，
find length比要把整个path打出来稍微简单点，
今天刚研究这题
【在 g***j 的大作中提到】
: 这个经典题目
: Given two words (start and end), and a dictionary, find the length of
: shortest transformation sequence from start to end, such that:
: Only one letter can be changed at a time
: Each intermediate word must exist in the dictionary
: 我理解的就是构建一个图，如果两个单词之间只有一个字母不一样，就有路径，然后找
: 从start到end的最短路径，是这样的么？
: 但是，这个说起来容易写起来难啊，面试的时候难道还要写一个最短路径的算法么？
: 另外，这个图如何构建呢？如何快速的判断两个单词只有一个字母不一样呢？
: 以前以为很容易，动手开始写了才知道好难，至少不像平时面试的那种20行就可以搞定
|
M********n
发帖数: 34 | 3 直接recursion会容易点吧
循环
依次改变一个字母， 查找是否在dict内，
不再字典内， 返回；
在， lenght +1， 返回
记录最小值 |
n*******w
发帖数: 687 | 4 recrusion试过，5个字母的单词都算不出来。假设字典50w单词，长度为5的单词只有几
千个。
这题我这么算的
1 先从字典里边选出长度为要找的单词的所有单词
2 建立dict，key是单词本身，value是从start到这个单词的路径长度，初始值为
integer的最大值，假设是MAX。
3 dict[start] = 0； dict[end] = MAX
4 对于dict里边每一个单词cur_word，
如果dict[cur_word] != MAX， 改变cur_word的任一个字符得到next_word，看next_
word是不是在dict里边，如果存在则更新dict[next_word] =
min( dict[next_word], 1+ dict[cur_word] )
5 如果step 4没有任何改变，退出。输出dict[end]
实际上DP，也可以看做是，建图并且Dijkstra一起做。
python写的话，不超过20行。运行时间在半分钟之内。
【在 M********n 的大作中提到】
: 直接recursion会容易点吧
: 循环
: 依次改变一个字母， 查找是否在dict内，
: 不再字典内， 返回；
: 在， lenght +1， 返回
: 记录最小值
|
p*****2
发帖数: 21240 | |
n*******w
发帖数: 687 | 6 这个好。。。可以当做标准答案。
没必要严格的Dijkstra。
【在 p*****2 的大作中提到】
: BFS就可以了吧？
: http://blog.sina.com.cn/s/blog_b9285de20101j1xl.html
|
