在FragranceNet上买的贝佳斯绿泥可靠不?# Fashion - 美丽时尚
h*o
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
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