h**o
发帖数: 548 | 1 两题有什么本质区别使得你们会想到一题用DP, 另一题用BFS?
1. Edit Distance：
-----------------
Given two words word1 and word2, find the minimum number of steps required
to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
2. Word Ladder
-----------------
Given two words (start and end), and a dictionary, find the length of
shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary |
W*****8
发帖数: 186 | 2 第二个不能insert or delete，只能exchange。
所以第二个的可能性大大减少，不需要用DP，用BFS就可以解决。 |
g****o
发帖数: 547 | 3 我也有疑问 word ladder能不能用A*搜索 会不会比bfs要好
【在 h**o 的大作中提到】
: 两题有什么本质区别使得你们会想到一题用DP, 另一题用BFS?
: 1. Edit Distance：
: -----------------
: Given two words word1 and word2, find the minimum number of steps required
: to convert word1 to word2. (each operation is counted as 1 step.)
: You have the following 3 operations permitted on a word:
: a) Insert a character
: b) Delete a character
: c) Replace a character
: 2. Word Ladder
|
h**o
发帖数: 548 | 4 Thanks
【在 W*****8 的大作中提到】
: 第二个不能insert or delete，只能exchange。
: 所以第二个的可能性大大减少，不需要用DP，用BFS就可以解决。
|
g*c
发帖数: 4510 | 5 好问题
都有source和target，都求最少多少步
【在 h**o 的大作中提到】
: 两题有什么本质区别使得你们会想到一题用DP, 另一题用BFS?
: 1. Edit Distance：
: -----------------
: Given two words word1 and word2, find the minimum number of steps required
: to convert word1 to word2. (each operation is counted as 1 step.)
: You have the following 3 operations permitted on a word:
: a) Insert a character
: b) Delete a character
: c) Replace a character
: 2. Word Ladder
|
