r****o
发帖数: 1950 | 1 以前的老题。
是不是要用到DFS/BFS啊？
有简单的方法吗？
Given a source word, a target word, and a dictionary, how to transform the
source word into target word by changing only one letter in each step. The
word you get in each step must be in the dictionary. | p*****e
发帖数: 1611 | 2 如果word短，dic很大的话，就穷举+hash+bfs
【在 r****o 的大作中提到】
: 以前的老题。
: 是不是要用到DFS/BFS啊？
: 有简单的方法吗？
: Given a source word, a target word, and a dictionary, how to transform the
: source word into target word by changing only one letter in each step. The
: word you get in each step must be in the dictionary.
| r****o
发帖数: 1950 | 3 为什么bfs还要用穷举呢？
【在 p*****e 的大作中提到】
: 如果word短，dic很大的话，就穷举+hash+bfs
| p*****e
发帖数: 1611 | 4 bfs的方式穷举。
你大概明白意思就好了~
这题关键是如果dic非常大，如果直接在dic上建图，是没法做的
【在 r****o 的大作中提到】
: 为什么bfs还要用穷举呢？
| f**r
发帖数: 865 | 5 Should we consider the following case, for e.g.: the dictionary contains 3
source word: boa
destination word: bbb
dictionary: boa, bbb, cbb, cob, coa
In this case, boa -> bbb cannot be achieved without changing the first
character (which were originally the same). It almost seems like some DP is
needed, or am I complicating things?
What is the tree that you guys search with BFS? |
|
