z***e
发帖数: 5393 | 1 题目：
从一个string 变到另一个，比如"study"->"world" （字数相等），要求
1. 每次变一个字母
2. 每次改变后的string必须是一个词典里面能查到的英语单词，比如你不能把study变
成atudy |
p***o
发帖数: 1252 | 2 5 min for the algorithm and 25 min for 50 lines of code?
impossible for fresh graduates ...
【在 z***e 的大作中提到】
: 题目：
: 从一个string 变到另一个，比如"study"->"world" （字数相等），要求
: 1. 每次变一个字母
: 2. 每次改变后的string必须是一个词典里面能查到的英语单词，比如你不能把study变
: 成atudy
|
z***e
发帖数: 5393 | 3 我当时misunderstood了一个条件，就是从s1->s2的时候，我最初以为是一个letter一
个letter地替换，保证每个替换后的词是valid的；后来才理解是可以从cat->cai->dai
->doi->dog这样子（打个比方）
算法就是不断地递归穷举，但是太多detail要handle了...
【在 p***o 的大作中提到】
: 5 min for the algorithm and 25 min for 50 lines of code?
: impossible for fresh graduates ...
|
p***o
发帖数: 1252 | 4 就是个graph traversal嘛，假设字典有了，用BFS估计20行能搞定，你用
DFS估计复杂点。
dai
【在 z***e 的大作中提到】
: 我当时misunderstood了一个条件，就是从s1->s2的时候，我最初以为是一个letter一
: 个letter地替换，保证每个替换后的词是valid的；后来才理解是可以从cat->cai->dai
: ->doi->dog这样子（打个比方）
: 算法就是不断地递归穷举，但是太多detail要handle了...
|
s*********b
发帖数: 815 | 5 Word ladder ah! Typical graph problem. See Knuth's classic The Stanford
GraphBase. The book is so fun to read. |
b*****j
发帖数: 1335 | 6 不可以吧，不是说每次都得换成valid的单词吗？
dai
【在 z***e 的大作中提到】
: 我当时misunderstood了一个条件，就是从s1->s2的时候，我最初以为是一个letter一
: 个letter地替换，保证每个替换后的词是valid的；后来才理解是可以从cat->cai->dai
: ->doi->dog这样子（打个比方）
: 算法就是不断地递归穷举，但是太多detail要handle了...
|
z***e
发帖数: 5393 | 7 每次换一个字母，保证结果是合法单词，不停换换到最后结果就行了。
pptwo说得对，是个graph traversal问题，问题是具体实现我觉得蛮花时间，毕竟这个
graph(dictionary)并不存在，要自己构造出来，就算bfs也很麻烦。
【在 b*****j 的大作中提到】
: 不可以吧，不是说每次都得换成valid的单词吗？
:
: dai
|
H*M
发帖数: 1268 | 8 这题半小时。。。。
什么公司这么夸张
【在 z***e 的大作中提到】
: 题目：
: 从一个string 变到另一个，比如"study"->"world" （字数相等），要求
: 1. 每次变一个字母
: 2. 每次改变后的string必须是一个词典里面能查到的英语单词，比如你不能把study变
: 成atudy
|
h*****0
发帖数: 4889 | 9 “每次改变后结果是合法的单词”
写得清清楚楚。
如果中间结果可以不合法，那随便弄啊，简直属于Hello world级别的题了。
【在 z***e 的大作中提到】
: 每次换一个字母，保证结果是合法单词，不停换换到最后结果就行了。
: pptwo说得对，是个graph traversal问题，问题是具体实现我觉得蛮花时间，毕竟这个
: graph(dictionary)并不存在，要自己构造出来，就算bfs也很麻烦。
|
g*****g
发帖数: 34805 | 10 I can find an algorighm that's probably not the best, but should
be easy to code in 30 minutes.
1. Use N^2 time to check if every 2 words in dictionary are connected.
if they do, give them a double link.
2. Start with your "study" word, and DFS the graph to see if
"world" can be reached.
【在 z***e 的大作中提到】
: 题目：
: 从一个string 变到另一个，比如"study"->"world" （字数相等），要求
: 1. 每次变一个字母
: 2. 每次改变后的string必须是一个词典里面能查到的英语单词，比如你不能把study变
: 成atudy
|
|
|
g*******y
发帖数: 1930 | 11 DFS跟BFS写起来差不多难度的
如果要求print 从original word 到 target word的一条path的话，DFS更直接方便一点
【在 p***o 的大作中提到】
: 就是个graph traversal嘛，假设字典有了，用BFS估计20行能搞定，你用
: DFS估计复杂点。
:
: dai
|
g*******y
发帖数: 1930 | 12 you can store nodes of strings using hash table. In my implementation of the Graph, it's something like:
struct Word_Graph{
hash_map index_map;
vector nodes;
int n;
vector> adj_list;
bool *visited;
void insert(const string &s);
bool DFS(string org, string target);
bool DFS_core(int s, int t);
};
then, when you insert a string(word) into a graph, you only need to do 26*word.length() queries in the hash table to see if the "
【在 g*****g 的大作中提到】
: I can find an algorighm that's probably not the best, but should
: be easy to code in 30 minutes.
: 1. Use N^2 time to check if every 2 words in dictionary are connected.
: if they do, give them a double link.
: 2. Start with your "study" word, and DFS the graph to see if
: "world" can be reached.
|
p***o
发帖数: 1252 | 13
the Graph, it's something like:
word.length() queries in the hash table to see if the "neighbor" word exists.
but you still need to perform such queries to build adj_list ...
【在 g*******y 的大作中提到】
: you can store nodes of strings using hash table. In my implementation of the Graph, it's something like:
: struct Word_Graph{
: hash_map index_map;
: vector nodes;
: int n;
: vector> adj_list;
: bool *visited;
: void insert(const string &s);
: bool DFS(string org, string target);
: bool DFS_core(int s, int t);
|
h*****0
发帖数: 4889 | 14 直接第二步就好了，遇到需要判断是否相连，就调用一次比较函数。
【在 g*****g 的大作中提到】
: I can find an algorighm that's probably not the best, but should
: be easy to code in 30 minutes.
: 1. Use N^2 time to check if every 2 words in dictionary are connected.
: if they do, give them a double link.
: 2. Start with your "study" word, and DFS the graph to see if
: "world" can be reached.
|
r*********r
发帖数: 3195 | 15 很典型的面试题.
DFS debug 起来比较麻烦一点.
BFS 用一个 queue, 可以打印一下中间结果, 帮助思考. |
g*****g
发帖数: 34805 | 16 If you don't do one, you don't have a graph,
and your probably end up doing more comparisons.
【在 h*****0 的大作中提到】
: 直接第二步就好了，遇到需要判断是否相连，就调用一次比较函数。
|
h*****0
发帖数: 4889 | 17 ok, at most, you can just store the comparison result after each time your
invoke the comparison function. anyway, depends on your method with the '
graph'.
【在 g*****g 的大作中提到】
: If you don't do one, you don't have a graph,
: and your probably end up doing more comparisons.
|
H*M
发帖数: 1268 | 18 faint..
dont understand. what is Word_Graph, word or graph?
wht bool* visited? why pointer?
index_map is used to store what?
What data structures do you assume for dictionary?
How do you convert the dictionary structure to graph?
ft..too many questions..
the Graph, it's something like:
【在 g*******y 的大作中提到】
: you can store nodes of strings using hash table. In my implementation of the Graph, it's something like:
: struct Word_Graph{
: hash_map index_map;
: vector nodes;
: int n;
: vector> adj_list;
: bool *visited;
: void insert(const string &s);
: bool DFS(string org, string target);
: bool DFS_core(int s, int t);
|
r****t
发帖数: 10904 | 19 one should build one of these, but need to be smarter, since dictionary can
have >130 k words, while words with the same length, say 4 characters, are
only several k in number.
【在 g*****g 的大作中提到】
: If you don't do one, you don't have a graph,
: and your probably end up doing more comparisons.
|
r****t
发帖数: 10904 | 20 BFS 算了 1412 步，不一定是最优解。半个小时是有可能的。
can
【在 r****t 的大作中提到】
: one should build one of these, but need to be smarter, since dictionary can
: have >130 k words, while words with the same length, say 4 characters, are
: only several k in number.
|
|
|
z****e
发帖数: 2024 | 21 恩，不一定最优，但是能作，要有面试的人提醒。
如果凭空给这么个题目，还真不容易。我要挂。
【在 r****t 的大作中提到】
: BFS 算了 1412 步，不一定是最优解。半个小时是有可能的。
:
: can
|
I**********s
发帖数: 441 | 22 这题我做过. 用的BFS, 每次从queue的前面拿到当前词, 把当前词变化之后, 如果在字
典里就加到queue后面. 如此一直到找到为止. 代码如下. 我第一次做这题花了大约两
小时. 除非参加过ACM之类的强化训练, 不然半小时太过分了.
char * alphabet = "abcdefghijklmnopqrstuvwxyz";
int len_alphabet = strlen(alphabet);
class ww {
public:
string w;
ww * prev; // keep track of previous word.
ww(string & word, ww * prev_ww) : w(word), prev(prev_ww) {}
};
int find_path(string & a, string & b) {
deque q;
deque q_visited;
string w;
int i, j, len = a.length();
char c;
q.push_ |
G*****s
发帖数: 27 | 23 - 完全不考虑效率的情形下, 用 sbcl[0], 递归实现 DFS, 15分钟搞定[1];
- 不过这样遇到稍为大一点的字典[2]就会被指数增长挤爆.
- 加了一点简单的 heuristic 和优化后, 还是找到了答案[3].
- 若要找最短路径, 还得用 BFS 或 iterative deepening[4].
结果:
("study" "studs" "stuns" "shuns" "shuls" "sauls" "cauls" "cauld" "could"
"would" "world")
[0] http://sbcl.sourceforge.net/
[1] http://paste.lisp.org/display/112017
[2] http://addagram.mytestbench.com/WORD.LST
[3] http://paste.lisp.org/display/112017#1
[4] http://paste.lisp.org/display/112017#2 |
w***g
发帖数: 5958 | 24 典型的中学竞赛题，这种容易题要是半个小时还调不通的话基本上得奖就无望了。
【在 H*M 的大作中提到】
: 这题半小时。。。。
: 什么公司这么夸张
|
f*******y
发帖数: 988 | 25 这不是扯淡么
光写点靠谱的I/O code读字典文件都不够
估计半个小时做出来的不录取，写的code肯定不是production grade的
【在 z***e 的大作中提到】
: 题目：
: 从一个string 变到另一个，比如"study"->"world" （字数相等），要求
: 1. 每次变一个字母
: 2. 每次改变后的string必须是一个词典里面能查到的英语单词，比如你不能把study变
: 成atudy
|
P********e
发帖数: 2610 | 26 you deserve a 赞
【在 G*****s 的大作中提到】
: - 完全不考虑效率的情形下, 用 sbcl[0], 递归实现 DFS, 15分钟搞定[1];
: - 不过这样遇到稍为大一点的字典[2]就会被指数增长挤爆.
: - 加了一点简单的 heuristic 和优化后, 还是找到了答案[3].
: - 若要找最短路径, 还得用 BFS 或 iterative deepening[4].
: 结果:
: ("study" "studs" "stuns" "shuns" "shuls" "sauls" "cauls" "cauld" "could"
: "would" "world")
: [0] http://sbcl.sourceforge.net/
: [1] http://paste.lisp.org/display/112017
: [2] http://addagram.mytestbench.com/WORD.LST
|
z****e
发帖数: 2024 | 27 恩，不一定最优，但是能作，要有面试的人提醒。
如果凭空给这么个题目，还真不容易。我要挂。
【在 r****t 的大作中提到】
: BFS 算了 1412 步，不一定是最优解。半个小时是有可能的。
:
: can
|
I**********s
发帖数: 441 | 28 这题我做过. 用的BFS, 每次从queue的前面拿到当前词, 把当前词变化之后, 如果在字
典里就加到queue后面. 如此一直到找到为止. 代码如下. 我第一次做这题花了大约两
小时. 除非参加过ACM之类的强化训练, 不然半小时太过分了.
char * alphabet = "abcdefghijklmnopqrstuvwxyz";
int len_alphabet = strlen(alphabet);
class ww {
public:
string w;
ww * prev; // keep track of previous word.
ww(string & word, ww * prev_ww) : w(word), prev(prev_ww) {}
};
int find_path(string & a, string & b) {
deque q;
deque q_visited;
string w;
int i, j, len = a.length();
char c;
q.push_back(new ww(a, NULL));
while (! q.empty()) {
w = q.front()->w;
for (i = 0; i < len; i ++) {
c = w[i];
for (j = 0; j < len_alphabet; j ++) {
w[i] = alphabet[j];
if (w == b) { // The word b is found.
q.push_back(new ww(w, q.front()));
print_path(q.back());
return 1;
}
if (is_word_in_dictionary(w)) {
if (! is_word_in_deque(q, w) &&
! is_word_in_deque(q_visited, w)) {
q.push_back(new ww(w, q.front()));
}
}
}
w[i] = c;
}
q_visited.push_back(q.front());
q.pop_front();
}
return 0;
} |
G*****s
发帖数: 27 | 29 - 完全不考虑效率的情形下, 用 sbcl[0], 递归实现 DFS, 15分钟搞定[1];
- 不过这样遇到稍为大一点的字典[2]就会被指数增长挤爆.
- 加了一点简单的 heuristic 和优化后, 还是找到了答案[3].
- 若要找最短路径, 还得用 BFS 或 iterative deepening[4].
结果:
("study" "studs" "stuns" "shuns" "shuls" "sauls" "cauls" "cauld" "could"
"would" "world")
[0] http://sbcl.sourceforge.net/
[1] http://paste.lisp.org/display/112017
[2] http://addagram.mytestbench.com/WORD.LST
[3] http://paste.lisp.org/display/112017#1
[4] http://paste.lisp.org/display/112017#2 |
w***g
发帖数: 5958 | 30 典型的中学竞赛题，这种容易题要是半个小时还调不通的话基本上得奖就无望了。
【在 H*M 的大作中提到】
: 这题半小时。。。。
: 什么公司这么夸张
|
|
|
f*******y
发帖数: 988 | 31 这不是扯淡么
光写点靠谱的I/O code读字典文件都不够
估计半个小时做出来的不录取，写的code肯定不是production grade的
【在 z***e 的大作中提到】
: 题目：
: 从一个string 变到另一个，比如"study"->"world" （字数相等），要求
: 1. 每次变一个字母
: 2. 每次改变后的string必须是一个词典里面能查到的英语单词，比如你不能把study变
: 成atudy
|
P********e
发帖数: 2610 | 32 you deserve a 赞
【在 G*****s 的大作中提到】
: - 完全不考虑效率的情形下, 用 sbcl[0], 递归实现 DFS, 15分钟搞定[1];
: - 不过这样遇到稍为大一点的字典[2]就会被指数增长挤爆.
: - 加了一点简单的 heuristic 和优化后, 还是找到了答案[3].
: - 若要找最短路径, 还得用 BFS 或 iterative deepening[4].
: 结果:
: ("study" "studs" "stuns" "shuns" "shuls" "sauls" "cauls" "cauld" "could"
: "would" "world")
: [0] http://sbcl.sourceforge.net/
: [1] http://paste.lisp.org/display/112017
: [2] http://addagram.mytestbench.com/WORD.LST
|
k***t
发帖数: 276 | 33 Why is the ww *prev set but never get used in the program? Thx.
【在 I**********s 的大作中提到】
: 这题我做过. 用的BFS, 每次从queue的前面拿到当前词, 把当前词变化之后, 如果在字
: 典里就加到queue后面. 如此一直到找到为止. 代码如下. 我第一次做这题花了大约两
: 小时. 除非参加过ACM之类的强化训练, 不然半小时太过分了.
: char * alphabet = "abcdefghijklmnopqrstuvwxyz";
: int len_alphabet = strlen(alphabet);
: class ww {
: public:
: string w;
: ww * prev; // keep track of previous word.
: ww(string & word, ww * prev_ww) : w(word), prev(prev_ww) {}
|
I**********s
发帖数: 441 | 34 用到了, 在这里:
ww(string & word, ww * prev_ww) : w(word), prev(prev_ww) {} |
