FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
leetcode/algorithms/editDistance/editDistance.cpp at master · nuclearhacking/leetcode · GitHub
nuclearhacking
/
leetcode
Public
forked from
haoel/leetcode
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Wiki
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
leetcode
/
algorithms
/
editDistance
/
editDistance.cpp
Copy path
More file actions
More file actions
Latest commit
History
History
History
127 lines (116 loc) · 3.76 KB
Breadcrumbs
leetcode
/
algorithms
/
editDistance
/
editDistance.cpp
Copy path
File metadata and controls
127 lines (116 loc) · 3.76 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
//
Source : https://oj.leetcode.com/problems/edit-distance/
//
Author : Hao Chen
//
Date : 2014-08-22
/*
*********************************************************************************
*
* 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
*
*
*********************************************************************************
*/
#
include
<
iostream
>
#
include
<
string
>
#
include
<
vector
>
#
include
<
algorithm
>
using
namespace
std
;
/*
* Dynamic Programming
*
* Definitaion
*
* m[i][j] is minimal distance from word1[0..i] to word2[0..j]
*
* So,
*
* 1) if word1[i] == word2[j], then m[i][j] == m[i-1][j-1].
*
* 2) if word1[i] != word2[j], then we need to find which one below is minimal:
*
* min( m[i-1][j-1], m[i-1][j], m[i][j-1] )
*
* and +1 - current char need be changed.
*
* Let's take a look m[1][2] : "a" => "ab"
*
* +---+ +---+
* ''=> a | 1 | | 2 | '' => ab
* +---+ +---+
*
* +---+ +---+
* a => a | 0 | | 1 | a => ab
* +---+ +---+
*
* To know the minimal distance `a => ab`, we can get it from one of the following cases:
*
* 1) delete the last char in word1, minDistance( '' => ab ) + 1
* 2) delete the last char in word2, minDistance( a => a ) + 1
* 3) change the last char, minDistance( '' => a ) + 1
*
*
* For Example:
*
* word1="abb", word2="abccb"
*
* 1) Initialize the DP matrix as below:
*
* "" a b c c b
* "" 0 1 2 3 4 5
* a 1
* b 2
* b 3
*
* 2) Dynamic Programming
*
* "" a b c c b
* "" 0 1 2 3 4 5
* a 1 0 1 2 3 4
* b 2 1 0 1 2 3
* b 3 2 1 1 1 2
*
*/
int
min
(
int
x,
int
y,
int
z) {
return
std::min
(x,
std::min
(y,z));
}
int
minDistance
(string word1, string word2) {
int
n1 = word1.
size
();
int
n2 = word2.
size
();
if
(n1==
0
)
return
n2;
if
(n2==
0
)
return
n1;
vector< vector<
int
> >
m
(n1+
1
, vector<
int
>(n2+
1
));
for
(
int
i=
0
; i<m.
size
(); i++){
m[i][
0
] = i;
}
for
(
int
i=
0
; i<m[
0
].
size
(); i++) {
m[
0
][i]=i;
}
//
Dynamic Programming
int
row, col;
for
(row=
1
; row<m.
size
(); row++) {
for
(col=
1
; col<m[row].
size
(); col++){
if
(word1[row-
1
] == word2[col-
1
] ){
m[row][col] = m[row-
1
][col-
1
];
}
else
{
int
minValue =
min
(m[row-
1
][col-
1
], m[row-
1
][col], m[row][col-
1
]);
m[row][col] = minValue +
1
;
}
}
}
return
m[row-
1
][col-
1
];
}
int
main
(
int
argc,
char
**argv)
{
string word1=
"
abb
"
, word2=
"
abccb
"
;
if
(argc>
2
){
word1 = argv[
1
];
word2 = argv[
2
];
}
int
steps =
minDistance
(word1, word2);
cout << word1 <<
"
,
"
<< word2 <<
"
:
"
<< steps << endl;
return
0
;
}
Back
|
FazBrowse Home
|
New Git URL