H*M
发帖数: 1268 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: zlike (最终幻想), 信区: Programming
标 题: 这个题目能否半小时完成coding？
发信站: BBS 未名空间站 (Tue Dec 22 20:31:36 2009, 美东)
题目：
从一个string 变到另一个，比如"study"->"world" （字数相等），要求
1. 每次变一个字母
2. 每次改变后的string必须是一个词典里面能查到的英语单词，比如你不能把study变
成atudy |
v******k
发帖数: 808 | 2 typical social network type questions; and yes you can, given a free
dictionary for word-look-up |
g*******y
发帖数: 1930 | 3 这个确实比其他的面试题写起来稍微费些时间，花了我二十几分钟写好。
核心就是对所有同样长度的单词 build一个graph，如果两个单词只差一个字母，就建一条边连接她们。然后在graph里面做DFS。
【在 H*M 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 发信人: zlike (最终幻想), 信区: Programming
: 标 题: 这个题目能否半小时完成coding？
: 发信站: BBS 未名空间站 (Tue Dec 22 20:31:36 2009, 美东)
: 题目：
: 从一个string 变到另一个，比如"study"->"world" （字数相等），要求
: 1. 每次变一个字母
: 2. 每次改变后的string必须是一个词典里面能查到的英语单词，比如你不能把study变
: 成atudy
|
a****n
发帖数: 1887 | |
k***e
发帖数: 556 | 5 好像复杂度是sizeOfLengthIWords ^ 2 因为对每对单词都要check一次
唯一想到的好点的对每个字母穷举，结合hash 这也要用 LengthOfWord * 26 很难提高
ps，stl里面好像没有hash，还要自己写
建一条边连接她们。然后在graph里面做DFS。
【在 g*******y 的大作中提到】
: 这个确实比其他的面试题写起来稍微费些时间，花了我二十几分钟写好。
: 核心就是对所有同样长度的单词 build一个graph，如果两个单词只差一个字母，就建一条边连接她们。然后在graph里面做DFS。
|
g*******y
发帖数: 1930 | 6 STL里面没有，不过大部分的compiler应该都支持的
MS VS里面stdext::hash_map，（不过性能不好。。。）
其他的boost什么的提供的hash据说性能好些
要是算上自己写hash的话，那是真的不可能半小时写出来了
【在 k***e 的大作中提到】
: 好像复杂度是sizeOfLengthIWords ^ 2 因为对每对单词都要check一次
: 唯一想到的好点的对每个字母穷举，结合hash 这也要用 LengthOfWord * 26 很难提高
: ps，stl里面好像没有hash，还要自己写
:
: 建一条边连接她们。然后在graph里面做DFS。
|
p********7
发帖数: 549 | 7 我觉得用map挺好的，一般词典能有多少词？ 数M内存绝对就够了。 用map在数据不很
多的情况下，影响不大吧。面试不能直接用hash的函数么？ |
