等等我,主人! - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

等等我,主人!

等等我,主人!# Joke - 肚皮舞运动

g*j2013-02-18 08:02

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行就可以搞定
的题目
请问是我理解错了，还是有别的更加优化的算法？
谢谢了！

p*g2013-02-18 08:02

2 楼

v*t2013-02-18 08:02

3 楼

显然不是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行就可以搞定

r*e2013-02-18 08:02

4 楼

没有滑雪板？1

【在 p*********g 的大作中提到】

M*n2013-02-18 08:02

5 楼

直接recursion会容易点吧
循环
依次改变一个字母，查找是否在dict内，
不再字典内，返回；
在， lenght +1，返回
记录最小值

n*w2013-02-18 08:02

6 楼

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，返回
: 记录最小值