Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Expand file tree

/

editDistance.cpp

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
46 lines (41 loc) · 1.75 KB
/

editDistance.cpp

Copy path

File metadata and controls

46 lines (41 loc) · 1.75 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
leetcode Question 29: Edit Distance
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
Analysis:
At the first glance, we might think this is a DFS problem, but if we see it is hard to find a quick DFS thought and the problem requires some optimal result (here is the minimum), DP is a good direction to consider.
Actually this is a classic DP problem:
The state is: table[i][j]=minimum number steps convert word1[1:i] to word2[1:j] (here assume string starts from 1).
The optimal function is: table[i+1][j+1] = min [table[i][j]+1 or 0 (+1 if word1[i+1]==word2[j+1], else +0), table[i][j+1]+1, table[i+1][j]+1 ].
Initialization:
table[0][i] = i i=1:|word1| here 0 means "", any string convert to "" needs the length of string
table[j][0] = j i=1:|word2|
table[0][0]=0 "" convert to "" need 0 steps.
*/
class Solution {
public:
int minDistance(string word1, string word2) {
int s1 = word1.size();
int s2 = word2.size();
if (s1==0){return s2;}
if (s2==0){return s1;}
vector<vector<int> > w(s1+1,vector<int>(s2+1,0));
for (int i=0;i<=s1;i++){w[i][0]=i;}
for (int i=0;i<=s2;i++){w[0][i]=i;}
for (int i=1;i<=s1;i++){
for (int j=1;j<=s2;j++){
w[i][j]=min(w[i-1][j]+1,w[i][j-1]+1);
if (word1[i-1]==word2[j-1]){
w[i][j]=min(w[i-1][j-1],w[i][j]);
}else{
w[i][j]=min(w[i-1][j-1]+1,w[i][j]);
}
}
}
return w[s1][s2];
}
};
Morty Proxy This is a proxified and sanitized view of the page, visit original site.