s*****l
发帖数: 45 | 1 实在没想出啥好的解法，来请假大侠们一下。。
Three allowed operations: delete a character, insert a character, replace a
character.
Now given two words - word1 and word2 - find
the minimum number of steps required to convert word1 to word2 |
z*******y
发帖数: 578 | 2 这个是Dynamic Programming
自己想还是挺难想的
搜一下 Dynamic Programming Edit Distance |
d*******8
发帖数: 785 | 3 在Converting的过程中要不要保持这个word还是个词典中的单词？
如果是那样的话，好像只有对相差一个Char的单词网络中做BFS
如果要求Operations最少的话，比如insertion, replacement, deletion都有各自
的Penalty的话，就是sequence alignment，DP就可以了吧。
a
【在 s*****l 的大作中提到】
: 实在没想出啥好的解法，来请假大侠们一下。。
: Three allowed operations: delete a character, insert a character, replace a
: character.
: Now given two words - word1 and word2 - find
: the minimum number of steps required to convert word1 to word2
|
n*******e
发帖数: 111 | 4 classic Dynamic Programming problem
you may refer the following link:
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/
BTW: is this in on-site interview or phone interview?
a
【在 s*****l 的大作中提到】
: 实在没想出啥好的解法，来请假大侠们一下。。
: Three allowed operations: delete a character, insert a character, replace a
: character.
: Now given two words - word1 and word2 - find
: the minimum number of steps required to convert word1 to word2
|
g*******y
发帖数: 1930 | 5 这个是算法课动态规划那部分比较简单的作业题吧
replace a
【在 s*****l 的大作中提到】
: 实在没想出啥好的解法，来请假大侠们一下。。
: Three allowed operations: delete a character, insert a character, replace a
: character.
: Now given two words - word1 and word2 - find
: the minimum number of steps required to convert word1 to word2
|
