d********w
发帖数: 363 | 1 amazon好像出过此题，简单的说，就是一个原始字符串，一个目标串，求最少的变换的
路径，要求每次变化后的词都在一个字典中。
有些人说bfs，还是dijkstra算法？
下面是原题
// http://www.cs.duke.edu/csed/newapt/allwordladder.html
A word ladder is a sequence of words in which each word can be transformed
into the next word by changing one letter. For example, the word ladder
below changes 'lot' to 'log'.
lot dot dog log
This is not the shortest word-ladder between 'lot' and 'log' since the
former can be immediately changed to the latter yielding a word ladder of
length two:
lot log
The first and last words in a word ladder are the anchor rungs of the ladder
. Any other words are interior rungs. For example, there are three interior
rungs in the ladder below between 'smile' and 'evote'.
smile smite smote emote evote
In this problem you'll write a method that has parameters representing
potential interior rungs: an array of strings (these may by nonsense or
English words), and the anchor rungs --- two strings. Your code must
determine the shortest word ladder between the anchor rungs that uses at
least one interior rung, and the number of such ladders. Return an array
containing two ints: the first is the length of the shortest valid word
ladder and the second is the number of shortest ladders. If there are no
valid ladders return [0,0]. |
d********w
发帖数: 363 | 2 有种做法是遍历字典，对每个字典中的词和当前的串做比较，如果满足distance的要求
，可以继续深层搜索。但要标记当前词是否用过，如果下一层失败的话，还要把状态改
成not visited，应该怎么保存这个状态么？请高手指点
如果题目加上限制，不能直接遍历字典，只有一个接口，isInTheDictionary(str), 那
么只能去遍历可能的下一个单词，尝试次数应该是(26-1)*length，就可以继续搜索了。
find_path(String a, String b, Path_List):
if (a.equals(b))
return
for (int i = 0; i
for (int j = 0; j < 26; j++):
if (a[i] == ('a' + j))
continue;
String cur =a.substr(0, i) + ('a'+j) + a.substr(i+1, a.
length());
if (isInDictionary(cur))
。。。
【在 d********w 的大作中提到】
: amazon好像出过此题，简单的说，就是一个原始字符串，一个目标串，求最少的变换的
: 路径，要求每次变化后的词都在一个字典中。
: 有些人说bfs，还是dijkstra算法？
: 下面是原题
: // http://www.cs.duke.edu/csed/newapt/allwordladder.html
: A word ladder is a sequence of words in which each word can be transformed
: into the next word by changing one letter. For example, the word ladder
: below changes 'lot' to 'log'.
: lot dot dog log
: This is not the shortest word-ladder between 'lot' and 'log' since the
|
l*****a
发帖数: 14598 | 3 首先初始单词/终止单词长度要一致
然后将字典中所有具有相同长度的单词生成N*N matrix
a[i][j]=1 means word[i]can transfer to word[j] with replacing one letter
otherwise a[i][j]=0
so your question changed to whether there is a path
a[start]==> a[end]
do BFS with the matrix to see whether there is a path
了。
【在 d********w 的大作中提到】
: 有种做法是遍历字典，对每个字典中的词和当前的串做比较，如果满足distance的要求
: ，可以继续深层搜索。但要标记当前词是否用过，如果下一层失败的话，还要把状态改
: 成not visited，应该怎么保存这个状态么？请高手指点
: 如果题目加上限制，不能直接遍历字典，只有一个接口，isInTheDictionary(str), 那
: 么只能去遍历可能的下一个单词，尝试次数应该是(26-1)*length，就可以继续搜索了。
: find_path(String a, String b, Path_List):
: if (a.equals(b))
: return
: for (int i = 0; i: for (int j = 0; j < 26; j++):
|
c******n
发帖数: 4965 | 4 remember now, someone posted before
just transform each pair of words into an edge if they are different
only by 1 letter. and each word is a vertex.
then the quesition is basically the shortest path from one word to
another. i.e. u can use BFS or Dijkstra. BFS is enough since all the
weights are 1
transformed
ladder
the
【在 d********w 的大作中提到】
: amazon好像出过此题，简单的说，就是一个原始字符串，一个目标串，求最少的变换的
: 路径，要求每次变化后的词都在一个字典中。
: 有些人说bfs，还是dijkstra算法？
: 下面是原题
: // http://www.cs.duke.edu/csed/newapt/allwordladder.html
: A word ladder is a sequence of words in which each word can be transformed
: into the next word by changing one letter. For example, the word ladder
: below changes 'lot' to 'log'.
: lot dot dog log
: This is not the shortest word-ladder between 'lot' and 'log' since the
|
i**********e
发帖数: 1145 | 5 Looks like an interesting problem. I coded a C++ solution using BFS here. The distance between words (Levenshtein distance) is calculated using DP. Anyone who's interested can take a look here:
http://www.ideone.com/enbHZ
The main idea is using BFS (with the help of a queue) to search for the
shortest length ladder word sequence.
Some notes about the code:
- The transformed word (the final word that you want to transform to) must
be in the dictionary.
- "Your code must determine the shortest word ladder between the anchor
rungs that uses at least one interior rung". My code does not follow this
spec, but is easy to modify to satisfy this requirement.
- No limit on search depth. So it might loop on forever if there is no such
word ladder exists.
- The original problem statement requires only all words to be of same
length in the dictionary. My code does not have this requirement (ie, it is
based on levenshtein's edit distance, each step you can insert/change/remove
1 character).
- It doesn't store the path how you would get to the answer. You can modify it (with some effort) to store the path.
Three main functions: |
i**********e
发帖数: 1145 | |
d****j
发帖数: 293 | 7 我再抛砖引玉一下，目前仅有idea：
这个问题和“任意两个人之间最多有6个朋友”论断有一点关联。level越深，节点越多
是显而易见的。
记得有人问过还是在书上看到过，给定linkedin的关系数据库，如何判断给定两个人是
否有关系，几级的关系？
有人提出，“如果从两边同时互相找”，就能节省很多空间，因为 刚才的论断，最多
只需要从两个方向上各走3级即可，存储空间大大降低。
如果用在这个题目中，也许可以。
问题就是，如何证明两个长度为n的单词，其转换的最大上界是多少？
当然，如果最大上界太大了，也没有用处了 |
s********y
发帖数: 58 | |
