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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个经典题目 : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 直接recursion会容易点吧 : 循环 : 依次改变一个字母, 查找是否在dict内, : 不再字典内, 返回; : 在, lenght +1, 返回 : 记录最小值
|
p*****2 发帖数: 21240 | |
n*******w 发帖数: 687 | 6 这个好。。。可以当做标准答案。
没必要严格的Dijkstra。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : BFS就可以了吧? : http://blog.sina.com.cn/s/blog_b9285de20101j1xl.html
|